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

精选留言(159)

• 

  yaya

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

  作者回复: 👍

  2019-01-03

  27

  322
• 

  郭霖

  动态规划状态转移表解法： public int minCoins(int money) { if (money == 1 || money == 3 || money == 5) return 1; boolean [][] state = new boolean[money][money + 1]; if (money >= 1) state[0][1] = true; if (money >= 3) state[0][3] = true; if (money >= 5) state[0][5] = true; for (int i = 1; i < money; i++) { for (int j = 1; j <= money; j++) { if (state[i - 1][j]) { if (j + 1 <= money) state[i][j + 1] = true; if (j + 3 <= money) state[i][j + 3] = true; if (j + 5 <= money) state[i][j + 5] = true; if (state[i][money]) return i + 1; } } } return money; }

  2019-01-03

  10

  69
• 

  攻玉

  # 1. 回溯 : 太慢了 coin = 0 def minCoin(money): global coin if money == 1: return 1 if money == 2: return 2 if money == 3: return 1 if money == 4: return 2 if money == 5: return 1 # if money <= 0: return coin = 1 + min(minCoin(money-1) , minCoin(money-3) , minCoin(money-5)) print(money , coin) return coin print(minCoin(10)) # 2.写备忘录, 记录重复的递归项: # 速度提升不知道几十万倍 ! 缺点就是有递归层数的限制 , 超过最大递归层数(几百?)会报错 import numpy as np map = {} # 初始化一个 dict coin = 0 def minCoin(money): global coin # 先查表 : if money in map: # 如果在 map 的第一列里面 , 说明记录过. return map[money] # 直接返回 minCoin if money == 1: return 1 if money == 2: return 2 if money == 3: return 1 if money == 4: return 2 if money == 5: return 1 # if money <= 0: return coin = 1 + min(minCoin(money-1) , minCoin(money-3) , minCoin(money-5)) map[money] = coin # 放入map return coin print(minCoin(100)) print(map) ''' # 3.DP . ### 备忘录有了, 我们尝试根据递推公式 : # coin = 1 + min(minCoin(money-1) , minCoin(money-3) , minCoin(money-5)) ### 书写状态转移方程 : s = {} # 设 s 为状态数组 : s[1] ,s[2] ,s[3] ,s[4] ,s[5] = 1,2,1,2,1 def minCoinDP(money): for i in range(6,money+1): s[i] = 1+ min(s[i-1],s[i-3],s[i-5]) return s[money] print(minCoinDP(10000))

  2019-03-13

  4

  61
• 

  algo

  回溯算法实现矩阵最短路径会有边界问题，下面是修改后的代码。 private static int MIN_DIS = Integer.MAX_VALUE; public static void minDisByBT(int i, int j, int[][] w, int n, int distance) { distance += w[i][j]; if (i == n - 1 && j == n - 1) { if (distance < MIN_DIS) MIN_DIS = distance; return; } if (i < n - 1) { minDisByBT(i + 1, j, w, n, distance); } if (j < n - 1) { minDisByBT(i, j + 1, w, n, distance); } }

  2019-02-22

  4

  35
• 

  feifei

  经过一个星期的努力，这个动态规划终于有点感觉了，今天来做题，我也来试试解这个题目，在看了第一个童鞋的解法后，感觉这个写的太死了，再就是没有反推出哪些币的组合，我就自己来实现了下！ 我也想说动态规划的解，真不容易啊，我按照老师提供的方法，先使用回塑写出了暴力搜索，然后再画出了递归树，找到状态组合，然后才来写这个动态规划，感觉好复杂，不过吧，这个使用状态转移方程，我感觉更难，比这个递归还难写。。。。。。，最主要是这个状态想不到，但这个动态规划代码写完了，我又感觉能写方程了，我想哭。。。。。。。 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; }

  作者回复: 👍 都有这个似懂非懂的过程的 多练习 慢慢就有感觉了

  2019-01-06

  3

  31
• 

  邢世宝

  课后习题用leetcode-322验证自己实现是否正确

  2020-03-28

  

  21
• 

  煦暖

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

  作者回复: 嗯嗯 是的 笔误 抱歉

  2019-01-03

  

  14
• 

  攻玉

  import numpy as np 老师 , 那个回溯法的代码好像不太对 , 我用 python 写了一个 import sys minDist = sys.maxsize n = 4 # 这是个 4*4 的矩阵 . w = np.array([[0,3,5,9],[2,1,3,4],[5,2,6,7],[6,8,4,3]]) # dist = np.zeros((4,4)) # 定义 dist(i, j) 为到达点 (i,j) 的路径长度 # dist[i, j] = w[i,j] + min(dist[i-1, j] , dist[i, j-1]) def minDistBackTrace(i, j, dist, w, n): global minDist dist += w[i][j] if i==n -1 and j == n-1 : if dist < minDist: minDist = dist return if i < n-1: minDistBackTrace(i + 1, j, dist, w, n) if j < n-1: minDistBackTrace(i , j + 1, dist, w, n)

  2019-03-12

  3

  12
• 

  猫头鹰爱拿铁

  看了这一篇豁然开朗，上一篇的习题也会做了。感觉这些涉及多决策的习题基本上第一眼都能想到回溯法，但是用动态规划法就要好好想一想，关键还是老师说的动态转移方程式。我尝试用两种方法做了一遍，回溯法和动态规划法。 int minNum = Integer.MAX_VALUE; /** * 使用回溯法获取给定金额最小的硬币数量，调用时num为0 * * @param coinVal * 硬币值数组 * @param total * 指定的金额 * @param num * 每个解法所得到的硬币数量 */ public void getLeastCoinNumByBackTracking(int[] coinVal, int total, int num) { if (total == 0) { if (num < minNum) minNum = num; return; } for (int i = 0; i < coinVal.length; i++) { if (total - coinVal[i] >= 0) { getLeastCoinNumByBackTracking(coinVal, total - coinVal[i], num + 1); } } } /** * 使用动态规划法获取给定金额下最小的硬币数量 * * @param coinVal * 硬币值数组 * @param total * 给定金额 * @return 给定金额下最小的硬币数量 */ public int getLeastCoinNumByDP(int[] coinVal, int total) { // coinNum存放的是每个对应金额下最少硬币的最优解 int coinNum[] = new int[total + 1]; coinNum[0] = 0; //初始化coinNum数组，硬币值数组对应的值的硬币数量都为1 for (int i = 0; i < coinVal.length; i++) { coinNum[coinVal[i]] = 1; } for (int i = 1; i <= total; i++) { if (coinNum[i] == 0) { int minTemp = Integer.MAX_VALUE; // 获取每个i对应的最小硬币数值 for (int j = 0; j < coinVal.length; j++) { if (i - coinVal[j] > 0) { int v1 = coinNum[i - coinVal[j]] + 1; if (v1 < minTemp) { minTemp = v1; } } } coinNum[i] = minTemp; } } return coinNum[total]; }

  2019-01-08

  1

  11
• 

  菜菜

  老师，回溯法求矩阵最短路径的代码会出错，边界条件的问题

  2019-03-05

  

  7
• 

  乾坤瞬间

  我捋一下思路用 状态转移表法 1，首先这个问题适合用多阶段决策最优模型，不过唯一与前面的例子不同的是，这里的阶段不是很容易找，其实问题的期望实质上是保证走尽量少的阶段达到累计值到达期望值(9)，而我们前面接触的都是固定的阶段，所以从这一点上对动态规划的阶段概念又有了新认识 2，状态的定义，定义一个status[i][w]二维数组，i代表第i阶段，w表示第i阶段的累积值，且w不大于9.其实我把每一层的状态值定义为上一层的所有状态与本层的任一组合(1，3，5)的和这样我们就可以避免重复子结构(3->5与5->3的第二阶段的状态值都是8)的计算

  2019-11-24

  2

  6
• 

  随风

  看了这么久，很少留言、很多思考题也只停留在想的层面，很少去实现。刚好有点时间，把动态规则这个思考题想了一下，顺便用Java实现出来。 思考题：如上面值{1,3,5}凑9块钱的最小张数、我们可以分成3个阶段。 第一阶段：用1块钱，那么1块钱可以有1、2、3...9张这几种可能。 第二阶段：在第一阶段的金额还有张数上增加3元的 第三阶段：在第二阶段总金额上载增加5元的。 状态转移方程:Sum(n) = Sum(n-1) + v * num ,v表示当前阶段的面值，num表示当前阶段的张数。 代码实现如下： public class DynMoney { private static int minNum = Integer.MAX_VALUE; /** * Sum(n) = Sum(n-1) + v * num * @param sum 凑的总额 * @param v 钱的面额 * @return */ public static int minMoney(int sum,int v[]) { nextStep(0, 0, 0, sum, v); return minNum; } /** * @param n 钱的张数. * @param c 到那个阶段 * @param cv 凑的钱数 * @param sum 要凑的钱的总数 * @param v 面额 */ public static void nextStep(int n,int c, int cv,int sum,int v[]) { //金额凑够了 if (cv == sum) { minNum = Math.min(minNum, n); return; } //或者凑到最后阶段，没凑够总金额 if(c == v.length) { return; } //每个阶段，钱的张数，张数应该小与等于 凑的金额/面额 for(int j=0; j <= sum/v[c]; j++) { if(cv + v[c]*j <= sum) { //当前阶段凑的不超额，下阶段继续凑 nextStep(n+j, c+1,cv + v[c]*j, sum,v); } } } public static void main(String arg[]) { System.out.println(minMoney(8, new int[]{1,3,5})); } }

  2019-02-14

  2

  5
• 

  星夜

  思考题接着码： 2.动态规划版本 private int coinPlan2(int[] coinTypes, int money) { int[] dp = new int[money + 1]; Arrays.fill(dp, -1); dp[0] = 0; // 按照硬币面值排序 Arrays.sort(coinTypes); // 复杂度O(M * N), 递推公式: f(n) = f(n - max(coinTypes)) + 1 for (int i = 1; i <= money; i++) { // 从小问题开始解决，避免重复计算 for (int j = coinTypes.length - 1; j >= 0; j--) { if (coinTypes[j] <= i && dp[i - coinTypes[j]] >= 0) { dp[i] = dp[i - coinTypes[j]] + 1; break; } } } // 最少需要多少枚硬币 return dp[money]; }

  2020-11-01

  

  4
• 

  强劲九

  关于动态规划的练习，可以去 LeetCode 上看 liweiwei 的题解。他的题解做得非常的详细和用心，并且会给出不同问题相关题目。跟着把出现的问题解决了，应该能够有很大的提升。

  2020-05-21

  

  4
• 

  阿崔cxr

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

  作者回复: 我擦，我研究下

  2019-02-21

  2

  4
• 

  blacknhole

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

  作者回复: 已改 多谢指正

  2018-12-31

  

  4
• 

  Monday

  2018最后一次更新，我通读三遍跟上打卡了。本节理论归纳的很精简，适合动态规划求解的问题的特性：一个模型，三个特征。 一个模型：多阶段决策最优解 三个特征：最优子结构，无后效性，重复子问题。

  2018-12-31

  

  4
• 

  Kudo

  思考题解答 使用回溯法（python实现）： import sys min_count = sys.maxsize # 用于追踪最小值 def minCoinCount(i, values, amount, ca): ''' i: 硬币数量 values: 硬币面值数组 amount: 要凑的总价值 ca: current amount 当前价值 ''' global min_count if ca == amount or i == amount: # 总共amount步 if ca == amount and i < min_count: min_count = i return for v in values: # 依次考察每种币值 if ca + v <= amount: # 保证不超总值价 minCoinCount(i+1, values, amount, ca+v) # 使用方法 values = [1,3,5] minCoinCount(0, values, 9, 0) print(min_count)

  2019-01-04

  

  3
• 

  想当上帝的司机

  放假了还在更新 赞

  2018-12-31

  

  3
• 

  邢世宝

  老师给的回溯法跑不通 /** * 求(0, 0)到(n-1, n-1)的最小和 * * @param matrix 二维数组 * @param i 开始的行坐标 * @param j 开始的列坐标 * @param n 数组长度 * @param length 到达(i, j)节点的路径 */ private void minLength(int[][] matrix, int i, int j, int n, int length) { length = length + matrix[i][j]; if (j == n - 1 && i == n - 1) { if (length < minLength) { minLength = length; } return; } if (i < n - 1) { minLength(matrix, i + 1, j, n, length); } if (j < n - 1) { minLength(matrix, i, j + 1, n, length); } }

  2020-03-28

  

  2