本篇博客为动态规的基础篇,从零开始学习动态规划,如有错误,请指正。
动态规划简称DP,核心思想是将原问题分解为相互重叠的子问题,通过解决这些子问题来解决原问题。在解决每个子问题后,将其解存储起来,避免重复计算,以提高效率。
动态规划通常适用于以下类型的问题:
通常情况下,使用动态规划来解决问题需要满足以下几个条件:
解题步骤:
dp[i]=?
实际上,光听这些理论的解题步骤,在做题的时候还是不会,接下来,将会从基础篇入手,来学动态规划算法。
泰波那契序列 Tn 定义如下:
T0 = 0, T1 = 1, T2 = 1, 且在 n >= 0 的条件下 Tn+3 = Tn + Tn+1 + Tn+2
给你整数 n,请返回第 n 个泰波那契数 Tn 的值。
示例 1: 输入:n = 4 输出:4 解释: T_3 = 0 + 1 + 1 = 2 T_4 = 1 + 1 + 2 = 4
示例 2: 输入:n = 25 输出:1389537
dp[i]
表⽰:第i
个泰波那契数的值。dp[i]=dp[i-1]+dp[i-2]+dp[i-3]
dp[i]
在 i = 0
以及i = 1
的时候是没有办法进⾏推导的,因为dp[-2]
或dp[-1]
不是⼀个有效的数据。因此我们需要在填表之前,将0, 1, 2
位置的值初始化。题⽬中已经告诉我们dp[0] = 0
,dp[1] = dp[2] = 1
dp[n]
的值class Solution {
int dp[40];
public:
int tribonacci(int n) {
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]; //返回值
}
};
三步问题。有个小孩正在上楼梯,楼梯有n阶台阶,小孩一次可以上1阶、2阶或3阶。实现一种方法,计算小孩有多少种上楼梯的方式。结果可能很大,你需要对结果模1000000007。 示例1: 输入:n = 3 输出:4 说明: 有四种走法
示例2: 输入:n = 5 输出:13
dp[i]
表示到达第i
个台阶时,有多少种方法
dp[i]=dp[i-1]+dp[i-2]+dp[i-3]
可以从分别从i-1
、i-2
、i-3
到达i
dp[i]
在i = 0
, i = 1
以及i = 2
的时候是没有办法进⾏推导的,因为dp[-3]
、dp[-2]
或dp[-1]
不是⼀个有效的数据。
因此我们需要在填表之前,将1, 2, 3
位置的值初始化。
根据题意, dp[1] = 1
, dp[2] = 2
, dp[3] = 4
dp[n]
的值
class Solution {
public:
int MOD=1e9+7;
int waysToStep(int n) {
if(n==1||n==2) return n; //处理一下边界情况
if(n==3) return 4;
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];
}
};
给你一个整数数组 cost ,其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用,即可选择向上爬一个或者两个台阶。
你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。
请你计算并返回达到楼梯顶部的最低花费。
示例 1: 输入:cost = [10,15,20] 输出:15 解释:你将从下标为 1 的台阶开始。
示例 2: 输入:cost = [1,100,1,1,1,100,1,1,100,1] 输出:6
dp[i]
表示从i
位置出发,到达楼顶的最小花费1cost[i]
,往后⾛⼀步,接下来从i + 1
的位置出发到终点: dp[i + 1] + cost[i]
;
▪ ⽀付cost[i]
,往后⾛两步,接下来从i + 2
的位置出发到终点: dp[i + 2] + cost[i]
dp[n - 1] = cost[n - 1]
, dp[n - 2] = cost[n - 2]
dp[1]
和dp[0]
的最小值class Solution {
public:
int minCostClimbingStairs(vector<int>& cost) {
int n=cost.size();
vector<int> dp(n+1,0);
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[1],dp[0]);
}
};
一条包含字母 A-Z 的消息通过以下映射进行了 编码 :
‘A’ -> “1” ‘B’ -> “2” … ‘Z’ -> “26” 要 解码 已编码的消息,所有数字必须基于上述映射的方法,反向映射回字母(可能有多种方法)。例如,“11106” 可以映射为:
“AAJF” ,将消息分组为 (1 1 10 6) “KJF” ,将消息分组为 (11 10 6) 注意,消息不能分组为 (1 11 06) ,因为 “06” 不能映射为 “F” ,这是由于 “6” 和 “06” 在映射中并不等价。
给你一个只含数字的 非空 字符串 s ,请计算并返回 解码 方法的 总数 。
示例 1: 输入:s = “12” 输出:2 解释:它可以解码为 “AB”(1 2)或者 “L”(12)。
示例 2: 输入:s = “226” 输出:3 解释:它可以解码为 “BZ” (2 26), “VF” (22 6), 或者 “BBF” (2 2 6) 。
示例 3: 输入:s = “06” 输出:0 解释:“06” 无法映射到 “F” ,因为存在前导零(“6” 和 “06” 并不等价)。
dp[i]
表示以i
位置结尾时,解码方法的总数s[i]
单独解码的时候:如果解码成功dp[i]+=dp[i-1]
;如果解码失败就是0
当s[i-1]
和s[i]
结合解码时:如果解码成功dp[i]+=dp[i-2]
;如果解码失败就是0dp[n-1]
class Solution {
public:
int numDecodings(string s) {
int n=s.size();
vector<int> dp(n,0);
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];
}
};