41 | 动态规划理论：一篇文章带你彻底搞懂最优子结构、无后效性和重复子问题

可以看做爬阶梯问题，分别可以走1.3.5步，怎么最少走到9步，动态转移方程为f(9)=1+min(f(8),f(6),f(4))

经过一个星期的努力，这个动态规划终于有点感觉了，今天来做题，我也来试试解这个题目，在看了第一个童鞋的解法后，感觉这个写的太死了，再就是没有反推出哪些币的组合，我就自己来实现了下！ 我也想说动态规划的解，真不容易啊，我按照老师提供的方法，先使用回塑写出了暴力搜索，然后再画出了递归树，找到状态组合，然后才来写这个动态规划，感觉好复杂，不过吧，这个使用状态转移方程，我感觉更难，比这个递归还难写。。。。。。，最主要是这个状态想不到，但这个动态规划代码写完了，我又感觉能写方程了，我想哭。。。。。。。 public int countMoneyMin(int[] moneyItems, int resultMemory) { if (null == moneyItems || moneyItems.length < 1) { return -1; } if (resultMemory < 1) { return -1; } // 计算遍历的层数，此按最小金额来支付即为最大层数 int levelNum = resultMemory / moneyItems[0]; int leng = moneyItems.length; int[][] status = new int[levelNum][resultMemory + 1]; // 初始化状态数组 for (int i = 0; i < levelNum; i++) { for (int j = 0; j < resultMemory + 1; j++) { status[i][j] = -1; } } // 将第一层的数数据填充 for (int i = 0; i < leng; i++) { status[0][moneyItems[i]] = moneyItems[i]; } int minNum = -1; // 计算推导状态 for (int i = 1; i < levelNum; i++) { // 推导出当前状态 for (int j = 0; j < resultMemory; j++) { if (status[i - 1][j] != -1) { // 遍历元素,进行累加 for (int k = 0; k < leng; k++) { if (j + moneyItems[k] <= resultMemory) { status[i][j + moneyItems[k]] = moneyItems[k]; } } } // 找到最小的张数 if (status[i][resultMemory] >= 0) { minNum = i + 1; break; } } if (minNum > 0) { break; } } int befValue = resultMemory; // 进行反推出，币的组合 for (int i = minNum - 1; i >= 0; i--) { for (int j = resultMemory; j >= 0; j--) { if (j == befValue) { System.out.println("当前的为:" + status[i][j]); befValue = befValue - status[i][j]; break; } } } return minNum; }

状态转移表法，二维状态表的图中，第一行下面的表达式： 文中“min(4+3, 8+3)”应该是“min(4+3, 9+3)”

老师，我按照文章里面的代码敲了一遍， 状态转移表法的那个代码运行结果等于 等于19 状态转移方程法的那个代码运行结果等于 18 不知道大家是不是这样的？？？？？？

状态转移方程法的代码实现有问题： 1，int minUp = Integer.MIN_VALUE;语句应赋值为Integer.MAX_VALUE。 2，返回前应将返回值赋值给mem[i][j]。

用动态规划的方法，初始化那些等于币值的价值，然后从1开始一步一步推到w元，f(k)代表k元时最少的硬币数量，状态方程是： f(k) = min(f(k-vi)) + 1, i需要遍历所有的币种。 另外，请问老师之后会多讲一些回溯的技巧吗？回溯方法虽然本身复杂度比较高，但是可以用一些剪枝技巧branch and bound，这样实际运行时间也能很快，而且很多复杂的问题用回溯法思路会比较简单。

大家做动态规划题目时会出现这种情况吗？在没看这些理论的知识时，不管什么最优子结构，重复子问题，也不管什么状态的时候，有些简单的问题自己还能解决，直到了解了这些知识，知道了什么是动态规划，了解了动态规划中状态转移的概念之后，我们往往在一个特别简单的问题上就去分析的很复杂以至于以前感觉很简单的问题现在都不会解了，感觉越做越不会了。。。

老师，回溯的那种解法，代码有问题，会出现数组越界，边界的问题。

为什么说存在重复子问题会更适合尝试动态规划来解决

小争哥，文章「状态转移方程法」中的代码，int minLeft = Integer.MAX_VALUE、int minUp = Integer.MAX_VALUE 是否存在问题。当计算到达（1,0）、(0,1) 两个点时，左右路径会变成初始的值，导致后续计算全部出错，是不是该初始化为 matrix[0] [0] 呢？ 这是我照着你思路实现的代码： ```java int[][] memo = null, matrix = null; public int minDistance2(int[][] matrix){ int len = matrix.length; this.matrix = matrix; // 转移方程法 memo = new int[len][len]; return minDistanceCore(len - 1, len - 1); } private int minDistanceCore(int row,int col) { if (row == 0 && col == 0) { // (0,0) 直接返回值 return matrix[0][0]; } if (memo[row][col] != 0) { // 若已计算则直接返回对应值 return memo[row][col]; } int distLeft = matrix[0][0], distUp = matrix[0][0]; if (col > 0) { distLeft = minDistanceCore(row, col - 1); } if (row > 0) { distUp = minDistanceCore(row - 1, col); } int curDist = matrix[row][col] + Integer.min(distLeft, distUp); memo[row][col] = curDist; // 记录当前距离 return curDist; } ```