R201142020-09-25课后思考题, class Solution { // 状态定义: dp[i] 表示截止到 nums 中 i 下标, 最大子数组和 // 状态转移: dp[i] = max(dp[i - 1] + nums[i], nums[i]) // 截止到数组的第 i 个下标, 子数组和的构成是下面两种情况结果中较大的值: // 1. 由截止到 i - 1 下标的最大子数组和与 nums[i] 构成 --> dp[i - 1] + nums[i] // 2. nums[i] // 结果是 max(dp[0]...dp[nums.length - 1]) public int maxSubArray(int[] nums) { if (nums == null) throw new IllegalArgumentException("nums can not be null!"); if (nums.length == 0) return 0; int[] dp = new int[nums.length]; dp[0] = nums[0]; int max = dp[0]; for (int i = 1; i < nums.length; i++) { dp[i] = Math.max(dp[i - 1] + nums[i], nums[i]); max = Math.max(dp[i], max); } return max; } } 时间复杂度: O(n) 空间复杂度: O(n) 空间优化: 在状态转移的过程中, 使用变量记录前一次状态和当前状态 class Solution { public int maxSubArray(int[] nums) { if (nums == null) throw new IllegalArgumentException("nums can not be null!"); if (nums.length == 0) return 0; int p = nums[0]; int max = p; for (int i = 1; i < nums.length; i++) { int t = Math.max(p + nums[i], nums[i]); max = Math.max(t, max); p = t; } return max; } }展开作者回复: 赞。顶上去！空间优化的思路是正确的。
共 2 条评论13
webmin2020-09-21最大和的连续子数组，一个数加正数会变大，加负数时会变小，关键的是正负是无规律出现的，且遇到负数也不一定就不能得到最大和的连续子数组（如：课后思考中的例子），通过观察我们可以发现当 sum(nums[0...i-1]) < nums[i]我们就选择nums[i]重新开始累加就好（ [-2, 1, -3, 1] -2+1+-3 < 1）,但是类似的这样区间可能会出现好多个，所以还需要一个变量来保存和比较历次区间和，最后此值就是最大和。 ```java public int maxSubArray(int[] nums) { int[] dp = new int[nums.length]; int maxSum = nums[0]; dp[0] = nums[0]; for(int i = 1; i < nums.length; i++){ //因为只需要记住前一个状态，所以这里是可以优化为一个变量来取代dp数组，这里是为了和老师课程dp示范呼应 dp[i] = Math.max(dp[i-1] + nums[i],nums[i]); maxSum = Math.max(maxSum,dp[i]); } return maxSum; } ```展开作者回复: 赞！
共 2 条评论5
追风筝的人2020-10-20老师 是不是自底向上的迭代处理思想 就是 动态规划的解决思路？作者回复: 差不多可以这么说。这是因为动态规划思想的核心就是用小问题的最优解去推导更大问题的最优解，最终通过组合子问题的最优解得到原问题的答案，自底向上很好的顺应了这一思想。同时，自底向上推导也符合状态转移方程的定义。所以这么说是恰到好处的。
共 2 条评论3
帽子狗2020-10-19这也太详细了.. 硬是三章引出来方程。 老师太贴心了。作者回复: 感谢你的肯定。事实上动态规划的提出正是从贪心算法开始的，为了让大家能够深刻理解动态规划的由来，我们有必要从贪心算法开始，再到穷举，最后再到动态规划。理解了其本质，才能说真正理解了动态规划。 不然，刷了再多题，看了再多讲解，也是空中楼阁，抓不住问题的根源，很难真正掌握这门手艺。
3
AshinInfo2020-09-29在动态规划中，我们将其称之为状态参数。同时，你应该注意到了，这个状态在不断逼近初始化状态。而这个不断逼近的过程，叫做状态转移。 这里的逼近初始状态，是自顶向下，这样说可以理解 但是如果是动态规划的话，是否这样说说比较好点 从初始状态不断的逼近目标状态作者回复: 你理解的很透彻！ 事实上，动态规划解法都是从小问题推广到大问题的，也就是你说的自底向上。虽然这里所说的是让计算逼近初始化状态，但其实真正的计算方向，是反过来的。
3
宋不肥2020-10-28自底向上递推，其实就是每一步都用贪心思想来向前贪心，向前贪心的好处是站在结果向前贪心，得到的就是之前各个最优解的选择，在这些最优解中必然包含了全局最优解，所以利用贪心可以得到全局最优解。第一步范围很小，贪心的局部最优就是全局最优。由数学归纳法，这样利用贪心往后递推，每一步向前贪心，每一步都是全局最优解，自底向上还省去了递归方法中判断多余分支的时间成本和开堆栈的空间成本（但其实现在计算机体系优化的很好了，个人感觉不是特别大的数据，这部分空间优化的开销感觉可以忽略）.作者回复: 对的。DP里肯定是用到了和贪心类似的“根据当前情况“求解”下一步的最优解“的思路。只不过DP是在分析问题的性质和结构后定义了一个正确的”贪心“函数，确保每一步的贪心（局部最优解）得到的就是这种状况下的全局最优解，只不过求解顺序肯定是自下向上而已。同时又利用缓存避免重复计算。 其实这里自底向上主要省去的还是时间成本。
2
Roy Liang2020-10-18int main() { int n, i, maxn = 0; int a[10000], b[10000]; cin >> n; for (i = 0; i < n; i++) { cin >> a[i]; maxn = min(a[i], maxn); } b[0] = a[0]; for (i = 1; i < n; i++) { b[i] = b[i-1] >= 0 ? b[i-1] + a[i] : a[i]; maxn = max(b[i], maxn); } cout << maxn << endl; }作者回复: 没有问题。赞。
1
fatty Jack2020-09-22//写了最基本的DP，参考了下大牛的代码，就是不一样 var maxSubArray = function(nums) { let ret = nums[0] //使用上一次的nums[i]存储dp状态 for (let i = 1; i < nums.length; i++) { //通过Math.max(nums[i - 1], 0)不需要区分大于/小于0的情况 nums[i] += Math.max(nums[i - 1], 0) ret = Math.max(ret, nums[i]) } return ret };作者回复: 这个解法没问题，但是有一个建议，即需要注意在解题的时候，最好不要就地修改输入数组的内容。这样做对性能损耗比较大。
1
Monroe He2022-11-08 来自北京# python version 3.7 import copy def max_sum_helper(values): # 初始化状态, 为其自身值 dp = copy.deepcopy(values) # 状态转移（参数变化） 改变状态表 values_length = len(values) for i in range(1,values_length): # 决策 tmp = values[i] if values[i]>=values[i]+dp[i-1] else values[i]+dp[i-1] dp[i] = tmp return max(dp) def get_max_sum(): # 数组 values = [-2, 1, -3, 1, -1, 6, 2, -5, 4] return max_sum_helper(values) # 输出答案 get_max_sum()作者回复: 顶一下，让其他人也能看到
😁2022-06-29「把备忘录中剩余的位置初始化成 k + 1」：这里不是初始化为-1的吗作者回复: 初始化为-1，是前面采用比较容易理解的递归+备忘录直接实现的时候。下面使用循环的动态规划中初始化的值是k+1。之所以不初始化为-1是因为后面需要取min，用k+1可以代表无穷大。