10 | 动态规划（下）：如何求得状态转移方程并进行编程实现？

精选留言(41)

• 云开

  2019-01-31

   7

  还是弄不明白编辑距离 为什么插入时是从空串开始 替换确并不计算从空串到有字符的过程

  作者回复: 你可以参考那张状态转移表，看看是从哪一格到哪一格，字符串是如何变换的，相邻格子的变换就三种方式，插入、删除和替换。替换可以将字符串中的某个字符替换成另一个字符

• 
  冰木

  2019-01-26

   4

  老大，我可能没有得到要领，可以推到下，表格中，第一行，第二列吗？

  作者回复: 是min(3, 1, 2)对吧，这个是mo和m的比较，3表示增加一个m再增加一个o，再删掉一个o，编辑距离是2+1=3。1表示两个字符串都是m，其中一个再增加一个o，编辑距离是1。2表示一个m增加o，一个从空集到m，编辑距离是2。你可以顺着第9讲最后的表格来推导。

• 
  我心留

  2019-01-05

   3

  public class Lesson10_2 {
  /**    
   * 动态规划求最小钱币数    
   * @param c 用一维数组记录每一步的总金额     * @param value 用一维数组记录三种面额的纸币    
   * @return     
   */    
  public static int getMinMoney(int[] c, int[] value) {
          int[] t = new int[3];        
                  for (int i = 0; i < c.length; i++) {        
                         for (int j = 0; j < value.length; j++) {                
                                if (i - value[j] >= 0) {                    
                                      t[j] = c[i - value[j]] + 1;                
                                 }            
                          }            
                    int min = Math.min(t[0], t[1]);            
                    min = Math.min(min, t[2]);            
                    c[i] = min;        
                  }        
                  return c[c.length - 1];
  }    
  public static void main(String[] args) {        
          int[] c = new int[100];        
          int[] value = new int[] { 2, 3, 7 };        
          System.out.println(getMinMoney(c, value)+1);    
   }
  }
  老师看一下代码对吗，运行结果是15

  展开

  作者回复: 代码的逻辑是对的

• lianlian

  2019-01-04

   3

  方法1，动态规划，最快。方法2递归有点慢，方法三递归，超级慢。在aim数值大于30的时候，三种写法，在我电脑速度快慢特别明显。用2元,3元,5元去找开100块，用递归方法，我的电脑要等到地老天荒O(∩_∩)O哈哈~
  #include<iostream>
  #include<vector>
  
  using namespace std;
  
  int dp_solve(int *a, int n, int aim){
      vector<vector<int>> dp(n, vector<int>(aim+1, 0));
  
      for(int j = 1; j <= aim; j++){
          dp[0][j] = INT_MAX;
          if(j >= a[0] && dp[0][j - a[0]] != INT_MAX)
              dp[0][j] = dp[0][j - a[0]] + 1;
      }
  
      for(int i = 1; i < n; i++){
          for(int j = 1; j <= aim; j++)
          {
              int tmp = INT_MAX;
              if(j - a[i] >= 0 && dp[i][j - a[i]] != INT_MAX)
                  tmp = dp[i][j - a[i]] + 1;
  
              dp[i][j] = min(dp[i-1][j], tmp);
          }
      }
  
      return dp[n-1][aim] == INT_MAX ? -1 : dp[n-1][aim];
  }
  
  int min_res = INT_MAX;
  void recur_solve(int *a, int n, int aim, int k){
      if(aim == 0){
          min_res = min(min_res, k);
          return;
      }
      if(aim < 0)
          return;
      for(int i = 0; i < n; i++){
          aim -= a[i];
          k++;
          recur_solve(a, n, aim, k);
          aim += a[i];
          k--;
      }
  }
  
  int min_res2 = INT_MAX;
  void recur_solve2(int *a, int n, int aim, vector<int> res){
      if(aim == 0){
          int size = res.size();
          min_res2 = min(min_res2, size);
          return;
      }
      if(aim < 0)
          return;
      for(int i = 0; i < n; i++){
          res.push_back(a[i]);
          recur_solve2(a, n, aim - a[i], res);
          res.pop_back();
      }
  }
  
  int main(){
      int a[] = {2,3,7};
      int sum = 25;
      /***dp最快**/
      cout << dp_solve(a, 3, sum) << endl;
  
      /***这种递归有点久**/
      recur_solve(a, 3, sum, 0);
      cout << min_res << endl;
  
      /**这个太久了**/
      vector<int> result;
      recur_solve2(a, 3, sum, result);
      cout << min_res2 << endl;
      return 0;
  }

  展开

  作者回复: 动手实验，比较不同的实现，👍

• 
  caohuan

  2019-01-21

   2

  本篇所得： 1.求解 最值可用动态规划 方法;
  2.状态转移 可以把 大问题 分解为 小问题，再分解为 可以处理的问题，即 把 不可以处理的问题 分解为可以 处理的小问题（ 也为子问题）;
  3.动态规划 适用于 下一个 状态与上一个状态有固定关系;
  4.搜索引擎的 搜索词的查询推荐， 英文可用 编辑距离，中文 需要 转化 比 如转为英文 再使用 编辑距离;
  5.从问题开始 ，初步分解 大问题为可解的子问题 为动态规划的方法，由问题 推到答案，也为反向思维法。
  
  回答老师的问题：固定金额，找最小钱币数量，可用倒推法，总金额 减去 最大的 钱币数额 ，然后从钱币中寻找该数额，没有 再把该数额逐渐减去 大的数额，一步步分解，可得 钱币的数量，该方法是 动态规划，但不能保证寻找的是最小的数量，局部最优 不一定全局最优，如果 需要寻找全部最优 需要运用 排列和组合。

  展开
• 
  mickey

  2019-01-04

   2

  package Part01;
  
  import java.util.ArrayList;
  import java.util.Arrays;
  import java.util.List;
  
  public class Lesson10_ex {
      public static void main(String[] args) {
          switchMoney(2, 3, 7, 100);
      }
  
      private static void switchMoney(int mz1, int mz2, int mz3, int total) {
          List<Integer[]> list = new ArrayList<Integer[]>();
          int s1 = total / mz1;
          int s2 = total / mz2 + 1;
          int s3 = total / mz3 + 1;
          for (int i = 0; i <= s1; i++) {
              for (int j = 0; j <= s2; j++) {
                  for (int k = 0; k <= s3; k++) {
                      if (mz1 * i + mz2 * j + mz3 * k == 100) {
                          list.add(new Integer[] { i, j, k });
                      }
                  }
              }
          }
          Integer[] result = new Integer[3];
          int min = total;
          for (Integer[] integers : list) {
              int sum = 0;
              for (Integer num : integers) {
                  sum += num;
              }
              if (min > sum) {
                  min = sum;
                  result = integers;
              }
          }
          System.out.println("最小数：" + min);
          System.out.println(Arrays.toString(result));
      }
  }
  

  展开
• 
  梅坊帝卿

  2019-01-04

   2

  按照面值排序优先取最大的方法 不一定能取到解 除非有万能的面额1 比如 2 5 7 总数15

  作者回复: 是的 可能无解👍

• 
  xiaobang

  2019-01-15

   1

  min的三个参数应该分别是插入删除替换，或者插入插入替换吧

  作者回复: 是的

• 
  Joe

  2019-01-14

   1

  1.C++实现，对总金额100的最小纸币是15.
  2.用递归法总金额为30就要算很久。
  3.另外的数学办法可以用总金额依次对最大金额纸币求余数，直到为0.商相加为答案。如：若 {1, 2, 3, 7}为纸币金额，对于100，所需最小纸币数：100/7=14余2; 2/2 = 1余0;则纸币数为14+1=15.
  
  // 动态规划问题
  #include <iostream>
  #include <string>
  #include <vector>
  using namespace std;
  
  class DynamicProgramming {
   private:
    vector<int> money = {1, 2, 3, 7}; // 纸币种类
  
   public:
    /**
     * Description: 对于金额固定，找出最少钱币数及方式。
     * prams: amountMoney- 输入总金额
     * return: 所需最小纸币数
     */
    int findFewerstMethod(int amountMoney) {
      int c[amountMoney];
      c[0] = 0;
  
      int temp;
      for (unsigned int i = 1; i < amountMoney; i++) {
        // 用最大值初始化
        int tempMin = amountMoney;
        for (unsigned int j = 0; j < money.size(); j++) {
          int diff = i - money[j];
          if (0 <= diff) {
            temp = c[diff] + 1;
          } else {
            // 此情况表示该纸币无效，选择最大值。
            temp = amountMoney;
          }
          // 求出最小值
          if (temp < tempMin) {
            tempMin = temp;
          }
        }
        c[i] = tempMin;
      }
  
      return c[amountMoney - 1];
    }
  };
  
  // test
  int main(void) {
    DynamicProgramming test;
    int res = test.findFewerstMethod(100);
    cout << res << endl;
    return 0;
  }

  展开

  作者回复: 答案正确 👍

• 
  assert

  2019-01-07

   1

  https://github.com/somenzz/geekbang/blob/master/mathOfProgramer/chapter10_dynamic_programming.py
  实现了循环和递归，循环的方式快，递归的方式特别慢。
  个人感觉递归是从后往前推导的，每一步的结果不论是否最优都保存在堆栈中，都占用了内存空间，算法上已经不属于动态规划。
  
  循环的方式不论 num 有多大，仅占用了7个变量的内存空间，每一步都保留上一步的最优解，因此效率较高，而且可以方便地打印出有最小数量的组合。
  
  循环方式的代码的输出如下：
   1 -> None
   2 -> (1, [2])
   3 -> (1, [3])
   4 -> (2, [2, 2])
   5 -> (2, [2, 3])
   6 -> (2, [3, 3])
   7 -> (1, [7])
   8 -> (3, [2, 3, 3])
   9 -> (2, [2, 7])
   10 -> (2, [3, 7])
   100 -> (15, [2, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7])
  
  
  

  展开

  作者回复: 确实，动态规划使用循环更快

• 
  菩提

  2019-01-06

   1

  思考题编码：
  public static int least_count(int num) {
          if (num < 0)
              return -1;
          int len = num;
          if (num < 9)
              len = 8;
          int[] c = new int[len + 1];
          c[0] = -1;
          c[1] = -1;
          c[2] = 1;
          c[3] = 1;
          c[4] = 2;
          c[5] = 2;
          c[6] = 2;
          c[7] = 1;
          c[8] = 3;
  
          if (num < 9) {
              return c[num];
          }
  
          for (int i = 9; i <= num; i++) {
              int a = c[i - 2] + 1;
              int b = c[i - 3] + 1;
              int min = Math.min(a, b);
              int m = c[i - 7] + 1;
              min = Math.min(min, m);
              c[i] = min;
          }
  
          return c[num];
      }
  
      public static void main(String[] args) {
          System.out.println(least_count(100));
      }
  
  运行结果： 15

  展开

  作者回复: 思路正确👍，编码可以稍微再通用点，用循环访问不同的币值

• lianlian

  2019-01-04

   1

  老师早上好( ^_^)／，在第一题求r的时候，条件判断语句应该是a.charAt(i+1) != b.charAt(j+1)吧😄 ？

  作者回复: 应该是i和j没错，只是这里的i和j对应于d[i+1][j+1]。这里比较容易让人混淆，主要是因为d中的0下表表示的是空串，而不是字符串中的第一个字符。我之后将代码注释加一下

• 奔跑的蜗牛

  2019-05-16

  

  老大 如果是第一行第三列呢？是+m+o+u-u-o吗？

  展开
• 
  jt

  2019-05-14

  

  c的来一个。
  
  #include <stdio.h>
  #include <stdlib.h>
  
  int min_piece(int sum, int *value, int num)
  {
      int *c, i, j, gap, tmp;
  
      c = malloc(sizeof(int) * (sum+1));
      c[0] = 0;
      for (i = 1; i <= sum; i++) {
          c[i] = 0;
          for (j = 0; j < num; j++) {
              gap = i - value[j];
              if (gap < 0) {
                  continue; /* 不存在 */
              } else if (gap == 0) {
                  c[i] = 1;
              } else if (gap < i) { /* 不应该超过i */
                  if (c[gap] <= 0) { continue; }
                  tmp = c[gap] + 1;
                  c[i] = (c[i] == 0 || c[i] > tmp) ? tmp : c[i];
              }
          }
          printf("-- %d: %d\n", i, c[i]);
      }
      tmp = c[sum];
      free(c);
      return tmp;
  }
  
  int main(void)
  {
      int sum = 30; /* 指定金额 */
      int value[] = {2,5,10}; /* 可选面额 */
  
      printf("need %d piece of money for %d yuan.\n",
             min_piece(sum, value, sizeof(value)/sizeof(int)), sum);
      return 0;
  }
  

  展开
• 
  You_can

  2019-04-07

  

  /**
   * 交作业
  * @param moneyCnt 钱币总金额
  * @param coinValue 钱币面额
  * @return int
   */
  public static int getCoinChangeLeastCnt(int moneyCnt, int[] coinValue) {
          if (moneyCnt <= 0) {
              return 0;
          }
  
          int[] cnt = new int[moneyCnt + 1];
  
          for (int i = 1; i <= moneyCnt; i++) {
              int minCnt = moneyCnt, tempValue =moneyCnt;
              for (int value : coinValue) {
                  if (value > i) {
                      tempValue = moneyCnt;
                  } else if (i - value >= 0){
                      tempValue = cnt[i - value] + 1;
                  }
                  if (tempValue < minCnt) {
                      minCnt = tempValue;
                  }
              }
  
              cnt[i] = minCnt;
          }
  
          return cnt[moneyCnt];
      }

  展开

  作者回复: 假期间坚持交作业，赞一个

• 
  叮当猫

  2019-04-05

  

  #include <vector>
  #include <iostream>
  using namespace std;
  
  int dpSolve(int * a, int n, int aim){
      vector<vector<int>> dp(aim+1, vector<int>(n+1, 0));
      for(int i=0; i<=aim; i++){
          int minvalue = INT_MAX;
          for(int j=0; j<n; j++){
              dp[i][j] = INT_MAX;
              if(i >= a[j]){
                  if(i % a[j] == 0)
                      dp[i][j] = i / a[j];
                  if(dp[i-a[j]][n] != INT_MAX)
                      dp[i][j] = min(dp[i-a[j]][n]+1, dp[i][j]);
                  if(minvalue > dp[i][j]){
                      minvalue = dp[i][j];
                  }
              }
          }
          dp[i][n] = minvalue;
      }
      return dp[aim][n];
  }
  
  int main(){
      int a[] = {1, 2, 5};
      int sum[] = {2, 5, 7, 10, 20, 100};
      for(int i=0; i<sizeof(sum)/sizeof(int); i++){
          cout << "sum:" << sum[i] << " " << dpSolve(a, 3, sum[i]) << endl;
      }
  }
  
  sum:2 1
  sum:5 1
  sum:7 2
  sum:10 2
  sum:20 4
  sum:100 20

  展开

  作者回复: 代码写得很赞

• 
  枫林火山

  2019-03-31

  

  对钱币问题经过循环，递归和动态规划的编码实践。作为一个数学菜鸟我有以下几个感触心得分享
  1. 递归方法。
  论性能是第一个就该出局的选择，但是他的分治思想是最容易理解和编码的。我觉得递归一个很大的作用是可以用快速得出的结果，帮助我们分析问题找出规律，来实现最优算法
  2. 循环方法。
  对于解这个问题时，循环编码的思路是我想的最久的，不像递归分治思想很快就出实现出来。循环的层数设置，跳出条件比较费脑子。最后我是用金额类别由大到小，依次嵌套循环遍历的方法实现的。这样的好处是找到的第一个解就是我需要的最优解。速度当然比递归快很多。
  3. 动态规划
  动态规划根据结果总结出转移方程后，他的编码实现比循环要简单。但是在实际多次逐步改大总金额设置试验后，发现动态规划的效率其实并没有上述的倒叙循环快。在设置金额10000时，循环打印0秒，动态规划42秒。
  总结原因是由于状态数过大造成，动态规划是稳扎稳打的实力派，每一步的结果都依赖上一次的状态结果，因此10000元相当于要从1逐步推导到10000.效率就没有”投机型“循环快了。
  因此我对动态规划程序做了第一步优化-尽可能完全的利用到已经计算的状态结果，
  比如创建初始状态时对最大金额的倍数金额 C[MaxAmount*k],及这个最有解的基础上可推出的其他(金额种类数-1)个状态 都直接填充了最优解结果,这样在动态规划过程中可直接跳过这些状态的最优解求解过程。
  此外还在动态规划推导中求得每个阶段最优解时，也同样填充了后面可以根据金额种类直接获得的最优解结果的状态
  经过上述优化后，时间从42秒降到了30秒，但是依然耗时高于循环。
  此时可以看到动态规划时间过长的根本原因还是其状态过多造成的，但是实际从结果可以看到我们应当是可以省略掉很多不必要的阶段求解的。需要将超多阶段数精减为一个最短阶段数的动态过程来处理。
  这部分我没有找到更好的办法，最后采用了循环用到的”投机法“，循环最小阶段动态规划，最终找到最短结果。
  总结：
  1. 动态规划的优点是可控制的循环复杂度，这个是一个定值。循环在本题中如果金额种类过多，性能应该会受到较大影响，而且编码思路不容易理清。
  2. 动态规划的最优解求法其性能是高于遍历的。如递归和未优化的循环
  3. 动态规划的缺点是当前结果依赖前一状态结果，状态阶段数太多的时候，会产生数量可控，但是很多的不必要中间结果
  4. 动态规划优化一定要尽可能的利用已计算的结果来减少状态求解数
  5. 根据实际题目和数学思想缩短状态阶段数目
  以上就是本节学习心得，发现了数据的魅力，有点后悔大学数据还给老师了。
  如果老师有看到，还有耐心读完，那么请教老师的问题是该题目的阶段数（总金额过大）时该如何优化。我大概猜的可能就是1.数学知识缩短状态阶段数 2.重新定义状态数。但是2个我都不知道怎么办=。=

  展开

  作者回复: 心得写得非常详细，赞一个。对于你最后的提问，我觉得暂时没有特别好的方法，除非我们可以接受某种近似解，并可以发现一种通过多个局部最优解能近似全局最优解的方法。

• 
  李凯

  2019-03-27

  

  黄老师您好 看不明白 您能讲一下 钱币组合表的8行和9行么 一行都没看懂

  作者回复: 第8行表示一共要8元，8元钱可以由6元钱加上1枚2元硬币，那么就是c(6)+1，而c(6)查看第6行的最后一列，是2，也就是说6元钱最少需要2枚硬币，所以8元钱如果是6元钱的硬币外加一枚2元硬币组成的话，那么最少需要(2+1)枚共3枚。不过，8元钱也可能由5元钱外加1枚3元硬币组成，所以我们还要看c(5)+1，其他的以此类推，最后确定8元钱最少需要多少钱币。

• 梦倚栏杆

  2019-03-23

  

  有点想数学的归纳演义的感觉

  展开
• 
  Lay Zhao

  2019-03-22

  

  交作业： 支持任意数量面额
  
  import Foundation
  
  import XCTest
  
  
  // 动态规划的经典模型-区间模型
  // 钱币组合
  // 给定总金额和可能的钱币面额，能否找出钱币数量最少的奖赏方式？
  // 假设这里我们有三种面额的钱币，2 元、3 元和 7 元。为了凑满100元最少的钱币数
  
  class DP05: XCTestCase {
      
      func countMoney(denomination: [Int], money: Int) -> Int {
          var c: [Int] = Array(repeating: -1, count: money + 1)
          
          for i in 1..<c.count {
              var d = -1
              for j in denomination {
                  if i < j { // 面额比钱多，不能采用
                      continue
                  }
                  if c[i-j] == -1 { // 减去当前面额，不能表示。
                      if i%j == 0 { // 刚好能被这种面额整除
                          d = i / j
                      }
                  } else {
                      // 动态转移方程，注意d > 0说明当前面额能被其他方案表示。
                      let new_d = c[i-j]+1
                      d = d > 0 ? min(d , new_d) : new_d
                  }
              }
              c[i] = d
          }
          for item in c.enumerated() {
              print(item)
          }
          
          return c[money]
      }
      
      func testCountMoney() {
          print(countMoney(denomination: [2,3,7], money: 100))
      }
  }

  展开

  作者回复: 代码很详细，可以再贴一下运行结果吗？