目录
一、算法简介
动态规划(Dynamic Programming)算法的核心思想是:将大问题划分为小问题进行解决,从而一步步获取最优解的处理算法
动态规划算法与分治算法类似,其基本思想也是将待求解问题分解成若干个子问题,先求解子问题,然后从这些子问题的解得到原问题的解。
与分治法不同的是,适合于用动态规划求解的问题,经分解得到的子问题往往不是互相独立的(即下一个子阶段的求解是建立在上一个子阶段的解的基础上)。
【Tips】动态规划算法解决问题的分类
- 计数:有多少种方式走到右下角 / 有多少种方法选出k个数使得和是 sum。
- 求最大值/最小值:从左上角走到右下角路径的最大数字和最长上升子序列长度。
- 求存在性:取石子游戏,先手是否必胜 / 能不能取出 k 个数字使得和是 sum。
【Tips】动态规划dp算法一般步骤
- 确定状态表示(dp[ i ] 的含义是什么,来源:1、题目要求;2、经验+题目要求;3、分析问题时发现重复子问题)
- 状态转移方程(可求得 dp[ i ] 的数学公式,来源:题目要求+状态表示)
- 初始化(dp 表中特别的初始值,保证填 dp 表时不会越界,来源:题目要求+状态表示)
- 填表顺序(根据状态转移方程修改 dp[ i ] 的方式,来源:题目要求+状态表示)
- 返回值(题目求解的结果,来源:题目要求+状态表示)
二、相关例题
1)第 N 个泰波那契数
.1- 题目解析
由题,题目的公式其实可以变形,从而得到如下公式:
由题,dp[i] 的含义可以是第 i 个泰波那契数的值,由此可得状态转移方程即为泰波那契数的公式:dp[i] = dp[i-1] + dp[i-2] + dp[i-3]。
特别的,第 0 个泰波那契数为 0,第 1 个和第 2 个泰波那契数为 1,也就是说 dp 表要做相应的初始化,即 dp[0] = 0、dp[1] = 1、dp[2] = 1。
在根据状态转移方程填 dp 表时,需要用到已经计算过的状态,那么填表顺序就是从左往右依次填表。
返回值则为第 N 个泰波那契数,即 dp[n]。
【补】滚动数组思想进行空间优化
假设有 a、b、c、d 四个变量,分别对应了泰波那契数列的前四个数,要求得第 n 个泰波那契数,只需让这四个变量按照如下方式,不断进行赋值操作即可:
- d = a + b + c;
- a = b;
- b = c;
- c = d;
在 a、b、c、d 不断向数列后面移动的过程中,这四个变量组成的一个序列就在数列中整体向后遍历。
.2- 代码编写
class Solution {
public:
int tribonacci(int n) {
if(n==0)return 0;//处理边界情况
if(n==1 || n==2)return 1;
vector<int> dp(n+1);
dp[0]=0,dp[1]=1,dp[2]=1;
for(int i=3;i<=n;i++)
dp[i]=dp[i-1]+dp[i-2]+dp[i-3];
return dp[n];
}
};
class Solution {
public:
int tribonacci(int n) {
if(n <= 1) // 处理边界
return n;
int a = 0, b = 1, c = 1, d = 1; // 滚动数组思想优化空间
for(int i = 3; i <= n; ++i)
{
d = a + b + c;
a = b;
b = c;
c = d;
}
return d;
}
};
2)三步问题
.1- 题目解析
以示例 1 为例,从楼梯下(即第 0 阶)上到第 1 阶,跨出一步即可,也就只有一种方式;
到第 2 阶可以一步一步地跨,也可以一次性跨两步,就有两种方式;到第 3 阶,可以一步一步跨,也可以一次性跨三步,还可以先跨一步再跨两边,或先跨两步再跨一步,一共有四种方式;到第 4 阶可以一步一步跨,或两步两步地跨,也可以先跨一步再跨三步,或先跨三步再跨一步,还可以先跨一步再跨一步再跨两步,或先跨一步再跨两步再跨一步,或先跨两步再跨一步再跨一步,一共有七种方式......以此类推,不难发现,从第 3 阶开始,相邻三阶各自的方式之和是下一阶的方式。
由此,dp[i] 的含义可以是上到第 i 阶的方式,而状态转移方程即为:dp[i] = dp[i-1] + dp[i-2] + dp[i-3]。
特别的,上到第 1 阶的方式为 1,第 2 阶的方式为 2,第 3 阶的方式为 4,也就是说 dp 表要做相应的初始化,即 dp[0] = 0、dp[1] = 1、dp[2] = 2、dp[3] = 4。
在根据状态转移方程填 dp 表时,需要用到已经计算过的状态,那么填表顺序就是从左往右依次填表。
返回值则为上到第 N 阶的方式,即 dp[n]。
.2- 代码编写
class Solution {
public:
int waysToStep(int n) {
if(n==1 ||n==2)return n;
if(n==3)return 4;
const int MOD=1e9+7;//按题目要求特殊处理结果
vector<int> dp(n+1);
dp[1]=1,dp[2]=2,dp[3]=4;
for(int i=4;i<=n;i++)
dp[i]=((dp[i-1]+dp[i-2])%MOD+dp[i-3])%MOD;//按题目要求特殊处理结果
return dp[n];
}
};
3)使用最小花费爬楼梯
.1- 题目解析
如果 dp[ i ] 表示到达 i 位置的最小花费,则到达dp[ i ] 就有以下两种情况:
- 先到达dp[ i-1 ] ,然后支付cost[ i-1] 到达 dp[ i ]。
- 先到达dp[ i-2 ] ,然后支付cost[ i-2] 到达 dp[ i ]。
题意及取两种情况小的那个,则得到状态转移方程:dp[i] =min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2])。此外,填表顺序为从左往右,要将第 0 阶和第 1 阶的花费初始化为 0,即dp[0]=0,dp[1]=0,返回值则为 dp[n]。
而如果 dp[ i ] 表示从 i 位置出发,到达楼顶,此时的最小花费,则dp[ i ] 就有以下两种情况:
- 支付 cost[ i ],往后走一步,从 i + 1的位置出发到终点。
- 支付 cost[ i ],往后走两步,从 i + 2的位置出发到终点。
则需要知道 i + 1 和 i + 2 位置的最小花费,及dp [i + 1] 和 dp[i + 2],那么就需要从右往左填,且状态转移方程为:dp[i] = min(dp[i+1] + cost[i], dp[i+2] + cost[i])。特别的,由于需要用到后两个已求得的状态来求当前状态,因此 dp 表的结尾两个位置就需要初始化,即 dp[n-1] = cost[n-1],dp[n-2] = cost[n-2];且返回值为 dp[0] 和 dp[1] 中的较小者。
.2- 代码编写
//dp[ i ] 表示到达 i 位置的最小花费
class Solution {
public:
int minCostClimbingStairs(vector<int>& cost) {
int n=cost.size();
vector<int> dp(n+1);
dp[0]=dp[1]=0;
for(int i=2;i<=n;i++)
dp[i]=min(dp[i-2]+cost[i-2],dp[i-1]+cost[i-1]);
return dp[n];
}
};
//dp[ i ] 表示从 i 位置出发,到达楼顶,此时的最小花费
class Solution {
public:
int minCostClimbingStairs(vector<int>& cost) {
int n=cost.size();
vector<int> dp(n+1);
dp[n-1]=cost[n-1],dp[n-2]=cost[n-2];
for(int i=n-3;i>=0;i--)
dp[i]=cost[i]+min(dp[i+1],dp[i+2]);
return min(dp[0],dp[1]);
}
};
4)解码方法
.1- 题目解析
dp[i] 可以表示,以 i 位置为结尾时,解码方法的总数。
关于 i 位置的编码状况,可以分为下面两种情况:
- 让 i 位置上的数单独解码成一个字母
- 让 i 位置上的数与 i - 1 位置上的数结合,解码成一个字母
如此,让 i 位置上的数单独解码成一个字母,就存在 解码成功 和 解码失败 两种情况:
- 解码成功:dp[i] = dp[i - 1],在 [0,i] 上所有解码结果后面填上一个字母即可。
- 解码失败:dp[i] = 0,前面努力都白费。
而让 i 位置上的数与 i - 1 位置上的数结合在⼀起,解码成一个字母,同样也存在解码成功和解码失败两种情况:
- 解码成功:dp[i] = dp[i - 2],在 [0,i] 上所有解码结果后面填上一个字母即可。
- 解码失败:dp[i] = 0,前面努力都白费。
综上,以 i 位置为结尾时解码方法的总数即为 dp[i] = dp[i - 1] + dp[i - 2],填表顺序为从左往右。
【补】处理边界情况和初始化问题的技巧
.2- 代码编写
class Solution {
public:
int numDecodings(string s) {
int n=s.size();
vector<int> dp(n);
dp[0]=s[0]!='0';
if(n==1)return dp[0];
if(s[0]!='0' && s[1]!='0')dp[1]+=1;
int t=(s[0]-'0')*10+s[1]-'0';
if(t>=10 && t<=26)dp[1]+=1;
for(int i=2;i<n;i++)
{
if(s[i]!='0')dp[i]+=dp[i-1];//处理单独编码的情况
int t=(s[i-1]-'0')*10+s[i]-'0';//处理结合编码的情况
if(t>=10 && t<=26)dp[i]+=dp[i-2];
}
return dp[n-1];
}
};
class Solution {
public:
int numDecodings(string s) {
int n=s.size();
vector<int> dp(n+1);
dp[0]=1;
dp[1]=s[1-1]!='0';
for(int i=2;i<=n;i++)
{
if(s[i-1]!='0')dp[i]+=dp[i-1];
int t=(s[i-2]-'0')*10+s[i-1]-'0';
if(t>=10 && t<=26)dp[i]+=dp[i-2];
}
return dp[n];
}
};