04 | 动态规划：完美解决硬币找零

课后思考题, 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; } }

最大和的连续子数组，一个数加正数会变大，加负数时会变小，关键的是正负是无规律出现的，且遇到负数也不一定就不能得到最大和的连续子数组（如：课后思考中的例子），通过观察我们可以发现当 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; } ```

老师 是不是自底向上的迭代处理思想 就是 动态规划的解决思路？

这也太详细了.. 硬是三章引出来方程。 老师太贴心了。

在动态规划中，我们将其称之为状态参数。同时，你应该注意到了，这个状态在不断逼近初始化状态。而这个不断逼近的过程，叫做状态转移。 这里的逼近初始状态，是自顶向下，这样说可以理解 但是如果是动态规划的话，是否这样说说比较好点 从初始状态不断的逼近目标状态

自底向上递推，其实就是每一步都用贪心思想来向前贪心，向前贪心的好处是站在结果向前贪心，得到的就是之前各个最优解的选择，在这些最优解中必然包含了全局最优解，所以利用贪心可以得到全局最优解。第一步范围很小，贪心的局部最优就是全局最优。由数学归纳法，这样利用贪心往后递推，每一步向前贪心，每一步都是全局最优解，自底向上还省去了递归方法中判断多余分支的时间成本和开堆栈的空间成本（但其实现在计算机体系优化的很好了，个人感觉不是特别大的数据，这部分空间优化的开销感觉可以忽略）.

int 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; }

//写了最基本的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 };

# 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()

「把备忘录中剩余的位置初始化成 k + 1」：这里不是初始化为-1的吗