动态规划题目特点

计数

  1. 有多少种方式走到右下角

  2. 有多少种方法选出k个数使其和为sum

    求最大最小值

  3. 从左上角走到右下角路径的最大数字和

  4. 最长上升子序列长度

    求存在性

  5. 取石子游戏，先手是否必胜

  6. 能不能选出k个数使得和使sum

动态规划组成部分

确定状态

  1. 状态在动态规划中的作用属于定海神针
  2. 简单地说，解动态规划的时候需要开一个数组，数组的每个元素f[i]或者f[i][j]代表什么
    1. 类似于解数学题中，X,Y,Z代表了什么
  3. 确定状态需要两个意识
    1. 最后一步：最优策略中的最后一个决策
    2. 子问题
      1. 一个例题：
        1. 最少用多少枚硬币可以拼出27*Ak
        2. 原问题是最少用多少枚硬币拼出27
        3. 我们将原问题转换成了一个子问题 而且规模更小 27-Ak
        4. 为了简化定义，我们设状态f(x)=最少用多少枚硬币拼出X
        5. image.png
        6. 如果Ak是2，f(27)应该是f(27-2)+1 加上最后一枚2的硬币
        7. 如果Ak是5，f(27)应该是f(27-5)+1 加上最后一枚5的硬币
        8. 如果Ak是7，f(27)应该是f(27-7)+1 加上最后一枚7的硬币

第一种递归解法

递归解法的问题：

做了很多次重复计算，效率低下
如何避免？

  1. 将计算的结果保存下来，并改变计算顺序

转移方程

  1. 设状态f[x]=最少用多少枚硬币拼出X
  2. 对于任何X
  3. 所以 总结f(27）=min{f(27-2)+1,f(27-5)+1,f(27-7)+1}
  4. image.png

初始条件和边界情况

  1. 所以 总结f(27）=min{f(27-2)+1,f(27-5)+1,f(27-7)+1}
  2. 两个问题
    1. X-2 X-5或者X-7<0怎么办？ 什么时候停下来
    2. 如果不能拼出Y，就定义f[Y]=正无穷
      1. 例如F[-1]=F[-2]=…..=正无穷
    3. 所以F[1]=min{f(-1)+1,f(-4)+1,f(-6)+1}=正无穷，表示拼不出来1
    4. 初始条件：F[0]=0
    5. 初始条件就是用转移方程算出来的 需要手工定义

计算顺序

拼出X所需要的最少硬币 f(27）=min{f(27-2)+1,f(27-5)+1,f(27-7)+1} X=27

  1. 初始条件:F[0]=0
  2. 然后计算f[1],f[2],f[3]….f[27]
  3. 当我们计算到f[X]时，f[x-2],f[x-5],f[x-7]都已经得到结果了

总结

  1. 每一步尝试三种硬币，一共27步
  2. 与递归算法相比，没有任何重复计算
  3. 算法时间复杂度 27*3
  4. 确定状态
    1. 最后一步：最有策略中使用的最后一枚硬币Ak
    2. 化成子问题：最少的硬币评出更小的面值27-Ak
  5. 转移方程：f(27）=min{f(27-2)+1,f(27-5)+1,f(27-7)+1}
  6. 初始条件和边界情况：F[0]=0,如果不能拼出Y,f[Y]=正无穷
  7. 计算顺讯：f[0],f[1],f[2]…f[x]

消除冗余，加速计算

动态规划:

  1. public int coinChange(int[] A,int M) {
  2.         int[] f = new int[M + 1];//从0开始
  3.         int n = A.length;
  4.         //初始化
  5.         f[0] = 0;
  6.         int i, j;
  7.         for (i = 1; i < M; ++i) {
  8.             f[i] = MAX_VALUE;
  9.             for (j = 0; j < n; ++j) {
  10.                 if (i > A[j] && f[i - A[j]] != Integer.MAX_VALUE) {
  11.                     f[i] = Math.min(f[i - A[j] + 1], f[i]);
  12.                 }
  13.             }
  15.         }
  16.         if (f[M] == MAX_VALUE){
  17.             f[M]=-1;
  18.         }
  19.         return f[M];
  20.     }

第二题

确定状态 v

  1. 最后一步：无论机器人用何种方式到达右下角，总有最后挪动的一步：向左或者向下
  2. image.png
  3. 右下角坐标设置为(m-1,n-1)
  4. 那么前一步机器人一定是在（m-2,n-1)或者(m-1,n-2)

  5. 设置子问题

    1. 那么如果机器人有X种方式从左上角走到(m-2,n-1)，有y种方式从左上角走到（m-1,n-2）则机器人有X+Y种方式走到(m-1,n-1)
    2. 思考：为什么是X+Y
    3. 子问题：
      1. 设f[i][j]为机器人有多少种方式从左上角走到(i,j)

        转移方程

  6. 对于任意一个格子(i,j)

    1. f[i][j] = f[i-1][j]+f[i][j-1]
    2. image.png

      初始条件和边界情况

  7. 初始条件 : f[0][0] = 1，因为机器人只有一种方式到左上角

  8. 边界情况：i=0或j=0，则前一步只能有一个方式过来 ==》f[i][j]=1

计算顺序

f[0][0] =1
计算第0行
计算第一行
计算。。。。
计算第m-1行
答案是f[m-1][n-1]
时间复杂度:O(MN)，空间复杂度（数组大小）：O(MN)

  1. public  int uniquePaths(int m,int n){
  2.         int[][] f=new int[m][n];
  3.         int i,j;
  4.         for (i = 0; i < m; ++i) {
  5.             for (j = 0; j < n; ++j) {
  6.                 if (i == 0 || j ==0){
  7.                     f[i][j] = 1;
  8.                 } else {
  9.                     f[i][j] =f[i-1][j]+f[i][j-1];
  10.                 }
  11.             }
  12.         }
  13.         return f[m-1][n-1];
  14.     }