题目链接

https://leetcode-cn.com/problems/predict-the-winner/

题目说明

题解

主要方法：递推；动态规划；前缀和

解释说明：

1. 求前缀和 pre_nums ，pre_nums[0] = 0, pre_nums[1+i] = sum(nums[0……i])

2. 动态规划、递推：

   • 数据表示：设立二维数组dp，dp[i][j]表示区间 [i,j] 内先取者能取得的最大值。dpnums
   • 初始状态：遍历 nums 数组求得长度为 1 的区间 [i,i] 内的最大值，即 dp[i][i] = nums[i]
   • 动态方程：先后遍历长度l,起点i，dp[i][j] [i,j]内最大值 = pre_nums[j+1]-pre_nums[i] nums[i,j]的总和 - min(dp[i][j-1] 取尾端，则减去下一个人相应的最大值[i,j-1], dp[i+1][j]) 取首端，则减去下一个人相应的最大值[i+1,j]；

3. 数据输出：比较全部最大值与总和的一半 return dp[0][size-1] >= sum/2

代码示例：

class Solution:

    def PredictTheWinner(self, nums: List[int]) -> bool:

        size = len(nums)

        # 求前缀和

        pre_nums = [0]

        for i in range(size):

            pre_nums.append(pre_nums[-1]+nums[i])

        dp, tmp = nums[:], []

        # 动态规划，这里 dp 数组降维，重复使用

        for l in range(2, size+1):

            tmp.clear()

            for i in range(size - l + 1):

                tmp.append(pre_nums[i+l] - pre_nums[i] - min(dp[i], dp[i+1]))

            dp = tmp[:]

        return dp[0] >= pre_nums[-1]/2

最新文章

1. HTML5 sessionStorage会话存储
2. Win32 OpenProcess打开进程失败，返回5无权限操作
3. 整理CSS引发的相关理论的梳理
4. Smallest Rectangle Enclosing Black Pixels
5. mysql数据库优化小结
6. C++多重继承子类和父类指针转换过程中的一个易错点
7. hive函数 -- split 字符串分割函数
8. [转] linux中巧用ctrl-z后台运行程序
9. android Init 相关分析
10. mysql 复杂的查询语句，工作中用到的记录下
11. JavaScript 核心参考教程 内置对象
12. getaccesstoken方法
13. Android应用性能优化方案
14. mybatis-databaseIdProvider多数据库支持
15. 最长公共子序列（POJ1458)
16. VS 编码规范---- 代码注释设置
17. Java开发笔记（五十四）内部类和嵌套类
18. 【Core内存】.NET Core 2.0中使用MemoryCache
19. EXPERT FOR SQL SERVER诊断系列--索引
20. 4、搭建Python环境

热门文章

1. Educational Codeforces Round 68 (Rated for Div. 2)-D. 1-2-K Game
2. Dungeon Master(三维bfs)
3. Math Problem（数学）
4. JVM—01
5. IE9 报错 script1004缺少“；”
6. Mockito在JUnit测试中的使用
7. Eclipse获取工作空间跟运行空间
8. 干Java这一行，应该怎样提升自己？
9. pytest封神之路第二步 132个命令行参数用法
10. 我是如何使用freemarker生成Word文件的?