动态规划 | Resume

常见的几种类型(动态规划的题目特点)

1. counting 计数

-有多少种办法走到右下角

-有多少种办法选出k个数使得其和为Sum

2.最大最小值

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

-最长上升子序列长度

3.求存在性

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

-能不能选出k个数的和是sum

例子：LintCode 669：coin change

说明：你有三枚硬币，分别面值2元，5元和7元，每种硬币都有足够多，而买一本书需要27元，如何用最少的硬币组合付清所有书钱而不需要对象找钱。

动态规划四个组成步骤：解决动态规划的四个部分

组成一：确定状态

状态的确定属于定海神针

简单来说，解动态规划的时候我们需要开一个数组，数组的每个元素f[i]或者f[i] [j]代表什么

—类似于解数学题中，x,y,z分别代表什么

确定状态需要两个意识：

-最后一步:在这个硬币题中，我们虽然不知道最优策略是什么，但是最优策略肯定是k枚硬币:$a_1,a_2,……a_k=27$,故一定有最后一枚

硬币：$a_k$,去掉这枚硬币前面所有的硬币面值加在一起是27-$a_k$

两个关键点：我们确定前面的硬币拼出了27-$a_k$,而且因为最优策略，前面用的硬币一定是最少的

-子问题:所以我们的问题就转化为最少用多少硬币可以拼出27-$a_k$，我们就将原问题化为了一个类型相似而且规模更小的子问题了：f(27-$a_k$),而最后一枚硬币只有三种可能，如果f(i)表示i元所需要的总次数，那么我们可以得到如下：

f(27)=min{f(27-2)+1,f(27-5)+1,f(27-7)+1}

那么我们根据上面的提示自然得到了递归的函数解法：

int f(int X){
  if(X==0)
    return 0;
  int res=MAX_VALUE;
  if(X>=2)
    return Math.min{f(X-2)+1,res;}
  if(X>=5)
    return Math.min{f(X-5)+1,res;}
  if(X>=7)
    return Math.min{f(X-7)+1,res;}
  return res;
}

递归解法的问题在于：重复调用（类似于分治我们会重复算所有的子情况,再说一点东西分治不能DP的原因就是因为子情况并不相同，子情况相同的时候产生的结果就是DP)

因此DP的做法：将计算结果保存下来，并改变计算顺序

组成二：转移方程

f(27)=min{f(27-2)+1,f(27-5)+1,f(27-7)+1}

组成三：初始条件和边界情况

这里的例题就有两个情况：x-2,x-5,x-7<0如何处理？什么时候才能停下来？

解决：如果不能拼出Y，就定义$f(Y)=+\infty$
-$f(-1)=f(-2)=…=+\infty$
故f(1)=min{f(-1)+1,f(-4)+1,f(-6)+1}=+∞，表示拼不出来

初始条件：f[0]=0,初始值的物理意义明确，按照其意义算即可

组成四：计算顺序

这里：按照从小到大的顺序去算

原则：要用到一个新的状态时，其他的子状态一定已经得到结果了

计算得到：
|…|f(-1)|f(0)|f(1)|f(2)|f(3)|f(4)|f(5)|f(6)|…|…|f(27)|
|:—|:—|:—|:—|:—|:—|:—|:—|:—|:—|:—|:—|
|$\infty$|$\infty$|0|$\infty$|1|$\infty$|2|…|…|…|…|…|

每一步尝试3种硬币：共27步,和递归相比没有任何重复的计算

public int coinChange(int []A,int M){
  int[]f=new int[M+1];//开数组的时候，如果要用到M就得开M+1
  int n=A.length;
  f[0]=0;
  int i,j;
  //f[1],f[2],f[3],......
  for(i=0;i<=M;++i){
    f[i]=Integer.MAX_VALUE;
    //last coin:A[1]?A[1]?A[2]?...A[n-1],即是哪一枚硬币
    //f[i]=min{f[i-A[0]]+1,......,f[i-A[n-1]]+1}
    for(j=0;j<n;++j)
    {
      if(i>=A[j]&&f[i-A[j]]!=Integer.MAX_VALUE)
        f[i]=Math.min{f[i],f[i-A[j]]+1};//+∞+1会跑到-∞去，因此不能用；防止出现负的情况
    }
  }
  if(f[M]==Integer.MAX_VALUE)
    return -1;//拼不出来的情况
  return f[M];
}

#[322]零钱兑换
class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        length = len(coins)
        DP = [amount+1]*(amount+1)
        DP[0] = 0
        for i in range(1, amount+1):
            count = 0
            while count < length:
                if i >= coins[count] and DP[i-coins[count]] != amount+1:
                    DP[i] = min(DP[i], DP[i-coins[count]]+1)
                count += 1
        if DP[amount] == amount+1:
            return -1
        return DP[amount]

例子2：LintCode 114：Unique Paths

题意：有m行n列的网格，机器人从左上角(0,0)出发，每一步可以向下或者向右走一步，问多少种不同的方法走到右下角

典型的记数型动态规划

步骤：

1.确定状态：最后一步:(m-2,n-1)+(m-1,n-2)=(m-1,n-1)(最后一部分)；子问题：(m-2,n-1)+(m-1,n-2)

2.转移方程：f[i] [j]=f[i-1] [j]+f[i] [j-1]

3.初始条件和边界情况

初始条件：f[0] [0]=0

边界条件：m=0,n=0;以及大于左右上下边界

答案：f[m-1] [n-1]

public int coinChange(int m,int n){
  int [][]f=new int[m][n];
  int i,j;
  for(i=0;i<m;++i){
    for(j=0;j<n;++j)
    {
      if(i==0||j==0)
        f[i][j]=1;
      f[i][j]=f[i][j-1]+f[i-1][j];
    }
  }
  return f[m-1][n-1];
}

#[56]不同路径
class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        # 确定状态
        DP = [[0 for i in range(n+1)] for i in range(m+1)]
        # 转移方程：DP[i][j]=DP[i][j-1]+DP[i-1][j]
        # 边界条件,我这里是额外扩展了一行一列
        DP[1][1] = 1
        for i in range(1, m+1):
            for j in range(1, n+1):
                DP[i][j] = DP[i][j-1]+DP[i-1][j]+DP[i][j]
        return DP[m][n]

#[63]不同路径II
class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
        m = len(obstacleGrid)
        n = len(obstacleGrid[0])
        DP = [[0 for i in range(n)] for i in range(m)]
        # 转移方程：DP[i][j]=DP[i][j-1]+DP[i-1][j]
        # 边界条件,我这里是额外扩展了一行一列
        count = 0
        while count < n and obstacleGrid[0][count] == 0:
            DP[0][count] = 1
            count += 1
        count = 0
        while count < m and obstacleGrid[count][0] == 0:
            DP[count][0] = 1
            count += 1
        for i in range(1, m):
            for j in range(1, n):
                if obstacleGrid[i][j-1] != 1:
                    DP[i][j] += DP[i][j-1]
                if obstacleGrid[i-1][j] != 1:
                    DP[i][j] += DP[i-1][j]
                if obstacleGrid[i][j] == 1:
                    DP[i][j] = 0
        return DP[m-1][n-1]

#[64]最小路径和
class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        m = len(grid)
        n = len(grid[0])
        DP = [[0 for i in range(n+1)]for i in range(m+1)]
        DP[0][0] = grid[0][0]
        for i in range(1, n):
            DP[0][i] = DP[0][i-1]+grid[0][i]
        for i in range(1, m):
            DP[i][0] = DP[i-1][0]+grid[i][0]
        for i in range(1, m):
            for j in range(1, n):
                DP[i][j] = min(DP[i][j-1], DP[i-1][j])+grid[i][j]
        return DP[m-1][n-1]

例子3：LintCode 116：Jump Game

有n块石头分别再x轴的0,1,2,……,n-1位置；一块青蛙在石头0，想跳到石头n-1，如果青蛙在第i块石头上，最多可以向右跳距离$a_i$,问请问能否跳到石头n-1上去

输入：a=[2,3,1,1,4]这样的数据

输出：True

输入：a=[3,2,1,0,4]这样的数据

输出：False

判断：存在型动态规划

步骤：

1.确定状态：最后一步:青蛙可以跳到石头i的同时最后一步距离不超过$a_i$

子问题：能不能跳到i

2.转移方程：$f[j]=OR_{0\leq i=j)$

一些解释：枚举前面所有0-j的石头，但是只需要里面的一块能够符合要求就行

3.初始条件和边界情况:

f[0]=True;因为青蛙一开始就在石头0

依次计算f[1],f[2],f[3],……f[n-1]

答案为f[n-1]

TC:$O(N^2)$
SC:O(N)

public boolean canJump(int []A){
  int n=A.length;
  boolean[] f=new boolean[n];
  f[0]=True;
  for(int j=1;j<n;++j){
    f[j]=false;
    for(int i=0;i<j;++i){
      if(f[i]&&i+A[i]>=j)
        {
        f[j]=true;
        break;
        }
      }
  }
  return f[n-1];
}

总结：四个步骤

确定状态：开数组
转移方程
边界条件
计算顺序

刷题顺序：https://leetcode.cn/problems/coin-change/solutions/2119065/jiao-ni-yi-bu-bu-si-kao-dong-tai-gui-hua-21m5