概念
- 动态规划的核心思想是把原问题分解成子问题进行求解,俗称大事化小,小事化了,简称DP
- 动态规划在代码上主常常以递归和循环的形式实现
动态规划 题目特点
- 计总数
62题 - 求最大值最小值
322题
152题 - 求是否存在
55题
403题 青蛙过河
动态规划 解题步骤
- 确认状态
明确最后一步做的事情,明确子问题是什么 - 建立转移方程
确定f(x)=? - 确定初始条件和边界情况
给整个计算确定一个起点
有些不属于转移方程的特殊情况需要额外定义
明确一些计算步骤取值边界 - 确定计算的顺序
动态规划 典型例题
1. (62力扣)在一个3 × 8的矩形网格,一个机器人从左上角走到由下角,机器人每次只能向下或者向右移动一步,总共有多少总路径?
| n1 | n2 | n3 | n4 | n5 | n6 | n7 | n8 |
|---|---|---|---|---|---|---|---|
| n9 | n10 | n11 | n12 | n13 | n14 | n15 | n16 |
| n17 | n18 | n19 | n20 | n21 | n22 | n23 | n24 |
在直观上,就是n1到n24,总共有多少总路径.
- 动态规划第一步是确认状态.
- 寻找问题的最后一个步骤
在表格上可以看出,到达n24位置,要不经过n16,要不经过n23,没有其他方式.
经过n16或n23就是到达n24的最后一步 - 确定子问题
所有到达n24的所有路径就被分成了两部分,即经过n16的和经过n23的
如果定义f(n24)=到达n24总共有多少个路径
那么 f(n24)= f(n16)+f(n23)
那么只要算出到达n16的路径数和到达n23的路径数,就能得到问题的答案了
确定的子问题应该与原问题存在联系,并且规模更小
考虑一下f(n16)和f(n23),同样的,可以发现
到达n16的路径数只有经过n8和n15两种方式
即 f(n16)= f(n8)+f(n15)
同理 f(n23)= f(n15)+f(n22)
这里确定下来的f(n)等于什么,就是所需要的状态
在这一阶段,需要判断要准备什么盒子(一维数组,二维数组或map等),盒子里放什么东西(子问题是什么,求什么结果)
虽然这个问题用一个24长度一维数组可以解决问题,但显然二维数组是最合适的
- 建立转移方程
按之前的思路,写出一个适配大多数情况的方程
f[i][j]= f[i-1][j] + f[i][j-1]
之前的 f(n24)= f(n16)+f(n23) 就可以表示为f[2][7]= f[1][7] + f[2][6] (数组从0开始)
3.确定转移方程的边界和初始条件
根据题干,很容易确定,i<3,j<8
下标不能为负数, i-1>=0,j-1>=0
对于下标为负数的,应该按0处理,没有任何路径会经过.
对于第一行和第一列的格子,只有一种方式,其值应为1
4.问题的处理顺序
一般分正序,倒序两种
正序从f[0][0]算到f[2][7],代码一般是通过for结构实现
倒序从f[2][7]算到f[0][0],通过递归调用不断深入
正序计算,适用于绝大部分数据都是有意义的情况,也就是数组里有赋值的下标比例比较多,并且存在很多的重复计算情况,是一般情况下采取的方式.
倒序计算,适合只有少部分数据是结果所需要的情况.
这个场景选择正序更加合适
(完整)在一个m×n的矩形网格,一个机器人从左上角走到由下角,机器人每次只能向下或者向右移动一步,总共有多少总路径?
class Solution {
public static int uniquePaths(int m, int n) {
int[][] dp=new int[m][n];
for(int i=0;i<dp.length;i++){
for(int j=0;j<dp[i].length;j++){
if(i==0 || j==0){
dp[i][j]=1;
}else{
dp[i][j]=dp[i][j-1]+dp[i-1][j];
}
}
}
return dp[m-1][n-1];
}
}
2.(322力扣)你有三种硬币,面值分别是2元,5元,7元,每种硬币数量足够多,一本书27元,最少用多少个硬币付清不找钱?
1.确认状态
定义f(x)=凑够x元最少的硬币数
因为面值分2,5,7三种
那么最后一步就是:
f(25)+一个2元 或 f(22)+一个5元 或 f(20)+一个7元
这三种情况的最小值
即f(27)=min{f(25)+1,f(22)+1,f(20)+1};
f(x)的值用int数组储存
- 建立转移方程
f(x)=min{f(x-2)+1,f(x-5)+1,f(x-7)+1};
3.确定转移方程的边界和初始条件
x-2,x-5,x-7>0
需要注意的是int[]的默认值是0,在计算最小值的时的时候有问题,需要设置成Integer.MAX_VALUE
4.确定计算顺序
正序
(完整) 给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。
你可以认为每种硬币的数量是无限的。
class Solution {
public int coinChange(int[] coins, int amount) {
int[] dp=new int[amount+1];
dp[0]=0;
for(int i=1;i<=amount;i++){
dp[i]=Integer.MAX_VALUE;
for(int j=0;j<coins.length;j++){
if(i>=coins[j]&&dp[i-coins[j]]!=Integer.MAX_VALUE){
dp[i]=Math.min(dp[i],dp[i-coins[j]]+1);
}
}
}
return dp[amount]==Integer.MAX_VALUE?-1:dp[amount];
}
}
除了动态规划的解法,纯粹的递归也是可行的,在剪枝后,效率相差不大,但是逻辑过于复杂
class Solution {
public static int coinChange(int[] coins, int amount) {
Arrays.sort(coins);
return coinChange_iteration(coins,0,coins.length-1,amount,-1);
}
public static int coinChange_iteration(int[] coins, int num, int curr_index, int surplus,int currMin) {
int remainder=surplus%coins[curr_index];
int division=surplus/coins[curr_index];
if(currMin!=-1&&num+division>currMin){
return currMin;
}
if(curr_index==0){
if(remainder==0){
currMin=currMin==-1?num+division:Math.min(currMin,num+division);
}
}else{
for(int i=0;i<=division;i++){
currMin=coinChange_iteration(coins,num+division-i,curr_index-1,remainder+(i*coins[curr_index]),currMin);
}
}
return currMin;
}
}
3.(力扣55)跳跃游戏
给定一个非负整数数组 nums ，你最初位于数组的 第一个下标 。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个下标。
示例 1：
输入：nums = [2,3,1,1,4]
输出：true
解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。
示例 2：
输入：nums = [3,2,1,0,4]
输出：false
解释：无论怎样，总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 ， 所以永远不可能到达最后一个下标。
按流程解题:
1.确定状态
找到一个可以跳到最后一个下标的位置,就说明跳到最后一个下标是可行.
这个位置需要满足当前位置加上当前位置可以跳跃的最大长度 大于或等于 最后一个下标值
以nums=[2,3,1,1,4]为例 ,最后的下标是4
当前位于下标3,那么3+nums[3]=4,那么这个条件就是满足的.
另外还要满足,当前位置是可以跳跃到的.
设f(x)=跳跃到下标x是否可行
那么f(4)=
至少一个为true{
f(0) && f(0)＋nums[0]>=4,
f(1) && f(1)＋nums[1]>=4,
f(2) && f(2)＋nums[2]>=4,
f(3) && f(3)＋nums[3]>=4
}
f(x)的值用boolean数组储存
2.建立转移方程
f(x)=
至少一个为true{
f(0 && f(0)＋nums[0]>=x,
f(1) && f(1)＋nums[1]>=x,
f(2) && f(2)＋nums[2]>=x,
......
f(x-1) && f(x-1)＋nums[x-1]>=x
}
抽象写法:
f(x)=OR(0<=y<x) {f(y) AND f(y)＋nums[y]>=x}
3.确认边界和初始条件
边界:f(x)的x为非负数
初始条件: f(0)=true
4.运算顺序
f(x)进行正序处理
里面的判断至少一个为true,使用倒序
代码:
class Solution {
public boolean canJump(int[] nums) {
boolean[] dp=new boolean[nums.length];
dp[0]=true;
i:for(int i=0;i<nums.length;i++){
j:for(int j=i-1;j>=0;j--){
if(dp[j]&&j+nums[j]>=i){
dp[i]=true;
break j;
}
}
}
return dp[nums.length-1];
}
}
5.403.青蛙过河
一只青蛙想要过河。 假定河流被等分为若干个单元格，并且在每一个单元格内都有可能放有一块石子（也有可能没有）。 青蛙可以跳上石子，但是不可以跳入水中。
给你石子的位置列表 stones（用单元格序号 升序 表示）， 请判定青蛙能否成功过河（即能否在最后一步跳至最后一块石子上）。
开始时， 青蛙默认已站在第一块石子上，并可以假定它第一步只能跳跃一个单位（即只能从单元格 1 跳至单元格 2 ）。
如果青蛙上一步跳跃了 k 个单位，那么它接下来的跳跃距离只能选择为 k - 1、k 或 k + 1 个单位。 另请注意，青蛙只能向前方（终点的方向）跳跃。
示例 1：
输入：stones = [0,1,3,5,6,8,12,17]
输出：true
解释：青蛙可以成功过河，按照如下方案跳跃：跳 1 个单位到第 2 块石子, 然后跳 2 个单位到第 3 块石子, 接着 跳 2 个单位到第 4 块石子, 然后跳 3 个单位到第 6 块石子, 跳 4 个单位到第 7 块石子, 最后，跳 5 个单位到第 8 个石子（即最后一块石子）。
示例 2：
输入：stones = [0,1,2,3,4,8,9,11]
输出：false
解释：这是因为第 5 和第 6 个石子之间的间距太大，没有可选的方案供青蛙跳跃过去。
1.确认状态
以stones = [0,1,3,5,6,8,12,17]为例
最后一步是青蛙从某个格子跳到了17位置,跳过来的格子的下标记为k
则K格子的位置是stones[k],设青蛙在k格子的上一次跳跃距离为len
根据题干可知K格子需要满足这些条件
- K格子是可达
- stones[k]+len-1=17 或者 stones[k]+len=17 或者 stones[k]+len+1=17
其中有两个变量,则可以设f(x,y)=上一次跳y格,是否可以到达stones[x]位置
数据结构可以选二维数组,也可以选HashMap<Integer,HashSet<Integer>>
2.转移方程
枚举出一个石头k,其中k满足 stones[k]=stones[x]-y
f(x,y)= f(k,y-1) || f(k,y) || f(k,y+1)
3.初始条件和边界
初始跳跃距离为1
最长跳跃距离为stones.length
4.顺序
正序
先枚举出f(x,y),再枚举找可跳的石头
class Solution {
public boolean canCross(int[] stones) {
boolean[][] isCan=new boolean[stones.length][stones.length];
if(stones[0]+1==stones[1]){
isCan[1][0]=true;
}else{
return false;
}
i:for(int i=1;i<isCan.length;i++){
j:for(int j=0;j<stones.length;j++){
if(isCan[i][j] ){
if(i==isCan.length-1){
return true;
}
k:for(int k=i+1;k<stones.length;k++){
int location=stones[k]-stones[i];
if(j<=location){
if(j==location){
isCan[k][j-1]=true;
}else if (j+1==location){
isCan[k][j]=true;
}else if (j+2==location){
isCan[k][j+1]=true;
break k;
}
}
}
}
}
}
return false;
}
}
