动态规划-从建表到切题(1)

本文对最值型、计数型、存在型、坐标型基础题目进行讲解

简介

动态规划（Dynamic Programming，DP），类似于高中学的数学归纳法，当我们计算dp[n]时，可以利用之前已经计算好的值来计算dp[n]。也可以理解成它是能够把递归计算中的重复计算减去的一种算法

动态规划题目的特点

1. 计数

• 有多少种方式走到右下角
• 有多少种方法选出k个数使和是Sum

  2. 求最大最小值

• 从左上角走到右下角路径的最大数字和
• 求最大上升子序列长度

  3. 求存在性

• 取石子游戏，先手能否胜利
• 能否选出k个数使和是Sum

求最值型动态规划

题目：零钱兑换

题意：给定几枚硬币，最少用几枚能拼出目标钱数

动态规划组成部分

1. 确定状态

• 最后一步： (最优策略中使用的最后一枚硬币$a_k$)
• 子问题： (最少的硬币拼出更小的面额$21-a_k$)

  2. 转移方程

  假设现在有2，5,7三种面额的钱
• $f[x] = min(f[x-2]+1,f[x-5]+1,f[x-7]+1)$

  3. 初始条件和边界情况

• 初始条件$f[0] = 0$,如果不能拼出Y,f[Y]=正无穷
• 无边界情况

  4. 程序

计数型动态规划

题目：不同路径

题意：给定一个m行n列的网格，一个机器人从左上角(0,0)位置出发，每次只能向右或向下走一步，问走多少种不同的方式从左上角走到右下角

动态规划组成部分

1. 确定状态

• 最后一步:无论机器人如何到达右下角，一定在上一步中挪过来的(向右或向下)
• 右下角坐标设为(m-1,n-1)
• 前一步一定在(m-2,n-1)或者(m-1,n-2)上
• 子问题：如果机器人有X种方式从左上角走到(m-2,n-1),Y种方式从左上角走到(m-1,n-2)，则机器人有X+Y种方式走到(m-1,n-1)
• 状态:设f[i][j]为机器人有多少种方式从左上角走到(i,j)

  2. 转移方程

• $f[i][j]=f[i-1][j]+f[i][j-1]$

  3. 初始条件和边界情况

• 初始条件：f[0][0]=1，机器人只有一种方式走到左上角
• 边界情况：f[i][0]=1,f[0][j]=1,每行每列只能一路走过来，因此也只有一种方式

  4. 程序

  进阶:不同路径2,地图有障碍
  程序

存在型动态规划

题目：跳跃游戏

题意：有n块石头分别在x轴的0,1，……，n-1位置，一只带黑框眼镜的青蛙在石头0上想跳到n-1上，如果ta在第i块石头上，ta最多可以向右跳距离$a_i$，问ta能否跳到n-1

例子：

• $输入：a=[2,3,1,1,4]$
• $输出：True$
• $输入：a=[3,2,1,0,4]$
• $输出：False$

  动态规划组成部分

  1. 确定状态

• 最后一步：如果能从i跳过来，那么青蛙一定能跳到i并且最后一步不超过能跳过来的最大距离$n-1-i<=a_i$
• 子问题：能否跳到当前位置
• 状态:设f[j]表示能否跳到石头j

  2. 转移方程

• $f[j]=OR_{0<=i<j}(f[i]ANDj-i>=a[i])$

  3. 初始条件和边界情况

• 初始条件：f[0]=True 第一块石头一定能跳上去
• 无边界情况

  4. 程序

  进阶：跳跃游戏2,需要找到跳每一个位置的最小值
  程序

坐标型动态规划

1. 题目：最长上升连续子序列

题意：给定一个数组，求出最长的连续子序列（单调上升或下降）

动态规划组成部分

1. 确定状态：

• 最后一步：对于最优策略，一定有最后一个元素a[j]，如果子序列长度大于1，那么最优策略a[j]的前一个元素肯定是a[j-1]，使得$a[j-1]<a[j]$
• 子问题： 要求以a[j]结尾的最长连续上升子序列,那么就要求以a[j-1]结尾的最长连续上升子序列
• 状态：设f[j]=以a[j]结尾的最长连续上升子序列的长度

  2. 转移方程

• $f[i]=max(1,f[i-1]+1ANDa[j-1]<a[j])$

  3. 初始条件和边界情况

• 初始条件：无
• 边界情况：前面的数存在，并且前面的数小于当前数

  4. 空间优化：

  由于转移方程只涉及到i与i-1,所以我们可以用一个长度为2的滚动数组优化

  int f[2],now=0,old=0;
  for(int i=0;i<n;i++){
      old=now;
      now=1-old;//交换顺序，滚动起来
  }

  5. 程序

---

2. 题目：最小路径和

题意：

• 给定m*n的网格，每个格子（i,j)里都有一个非负数A[i][j]

• 求一个从左上角到右下角的路径，每一步只能向右或向下走，求所有路径中最小的路径和

  动态规划组成部分

  1. 确定状态：

• 最后一步：一定是从上面或左面的总和最小过来的

• 子问题： 要求(m-1,n-1)的最小路径和，需要知道(m-1,n-2),(m-2,n-1)的最小路径和加上(m-1,n-1)的大小

• 状态：设从(0,0)走到(i,j)的最小数字总和f[i][j]

  2. 转移方程

• $f[i][j]=min(f[i-1][j],f[i][j-1])+A[i][j]$

  3. 初始条件和边界情况

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

• 边界情况：第一行和第一列只能从一个方向过来

  4. 空间优化：

  由于转移方程只涉及到两行或两列，所以我们可以用两行的滚动数组优化，详见戳我(～￣▽￣)→))￣▽￣)o

  3. 题目：炸弹袭击

  题意：

• 有一个M*N的网格，每个格子可能是空的，可能有一个敌人，可能有一堵墙

• 只能在某个空格子里放一个炸弹，炸弹会炸死所有同行同列的敌人，但是不能穿透墙，问最多能炸死几个敌人

  动态规划组成部分

  1. 确定状态：

• 假设：所有的格子都能放炸弹

  • 有敌人的格子：格子里的敌人被炸死并且能够继续向四周爆炸
  • 有墙的格子：炸弹炸不死任何人

• 在(i,j)格放一个炸弹，能够向上炸死的敌人数：（接下来以向上为例）

  • (i,j)为空地：能向上炸死(i-1,j)人
  • (i,j)为敌人:能向上炸死(i-1,j)+1人
  • (i,j)为墙：0

• 最后一步：无

• 子问题： 求(i,j)格能向上炸死的人数需要知道(i-1,j)格向上能炸死的敌人数

• 状态：Up[i][j]表示(i,j)格放一个炸弹向上能炸死的敌人数

  2. 转移方程

• $f[n]=\begin{cases}
  Up[i-1][j],&if(i,j)格是空地\
  Up[i-1][j]+1,&if(i,j)格是敌人\
  0,&if(i,j)格是墙\
  \end{cases}$

  3. 初始条件和边界情况

• 初始条件：如果(0,j)格不是敌人，Up[0][j]=0,如果是敌人Up[0][j]=1;

• 边界情况：同上

  4. 程序

赏

来根小鱼干好吗o( =·ω·= )m

支付宝

微信