动态规划:从入门到入土系列(二)
前言
一、使用最小花费爬楼梯
题目来源于:力扣 题目链接:传送门
(1) 题目描述
给你一个整数数组 cost ，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用，即可选择向上爬一个或者两个台阶。
你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。(表示开始费用为0)
目的:请你计算并返回达到楼梯顶部的最低花费。
示例:
示例 1：
输入：cost = [10,15,20] 输出：15
解释：你将从下标为 1 的台阶开始。 支付 15 ，向上爬两个台阶，到达楼梯顶部。 总花费为 15 。
示例 2：
输入：cost = [1,100,1,1,1,100,1,1,100,1] 输出：6
解释：你将从下标为 0 的台阶开始。 支付 1 ，向上爬两个台阶，到达下标为 2 的台阶。 支付 1 ，向上爬两个台阶，到达下标为 4 的台阶。 支付 1 ，向上爬两个台阶，到达下标为 6 的台阶。 支付 1 ，向上爬一个台阶，到达下标为 7 的台阶。 支付 1 ，向上爬两个台阶，到达下标为 9 的台阶。 支付 1 ，向上爬一个台阶，到达楼梯顶部。 总花费为 6 。
(2)解题思路
对于动态规划类的题目,都是有固定格式的,
- 确定状态表示.
- 创建dp表,
- 填写dp表(根据状态转移方程)
- 细节处理,是否越界?初始化等问题.
- 确认返回值.
状态表示
状态表示:
dp[n]表示到达,第下标为n阶楼梯的最小花费.
状态转移方程:
由于支付费用可以向前走一个或者两个台阶,那么到达当前台阶(n)有两种情况.
情况1:从第n-2阶,走两步到达. 情况2: 从第n-1阶走一步到达.
细节处理:
由于状态转移方程可能会发生越界访问,所以,需要对dp[0]和dp[1]处理.
还记得题干说的吗?可以从第一个台阶或者第二个台阶起步.
意味着,到达第一阶楼梯和第二阶楼梯的花费都是0.
返回值确认:
(3)代码展示:
class Solution {
public:
int minCostClimbingStairs(vector<int>& cost) {
int n=cost.size(); //获取cost表的长度
vector<int> dp(n+1); //创建dp表
//初始化
dp[0]=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]);
}
//返回值,此处楼顶应该是dp[n]
return dp[n];
}
};二、解码方法:
题目来源于:力扣 题目链接:传送门
(1)题目描述
一条包含字母 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” 并不等价）。
注意: 1 <= s.length <= 100 s 只包含数字，并且可能包含前导零。
(2)解题思路:
状态表示
dp[n]表示到达下标为n处,解码 方法的 总数.
状态转移方程:
细节处理:
要处理边界问题,状态转移方程中至少要确定前两个位置才能计算下一个.
dp[0]:单独编码,
成功:dp[0]=1;
失败: dp[0]=0;
dp[1]:单独编码:
成功:dp[1-1]=dp[0]
失败:方法+0
dp[0]与dp[1]:联合编码:
成功: 方法+1
失败: 方法+0
返回值确认:
dp[n-1]表示到达下标为n-1处,解码 方法的 总数,也就是到最后一个字母的解码总数.
(3)代码展示:
class Solution {
public:
int numDecodings(string s) {
int n=s.size(); //获取字符串s的长度
vector<int> dp(n); //创建一个n大小空间的vector(所有元素默认初始化为了0)
//初始化
//if(s[0]-'0'>0 && s[0]-'0'<=9) dp[0]=1; 写法1
//写法2
if(s[0]!='0')dp[0]=1; //因为该字符串只会出现数字,所以非0就是解码成功
if(n==1) return dp[0]; //特殊情况,s的长度为1
if(s[1]!='0') dp[1]=dp[0]; //dp[1]单独编码成功
//联合编码
int tmp=(s[0]-'0')*10+s[1]-'0';
if(tmp>=10 && tmp<=26)
{
dp[1]+=1;
}
//填表
for(int i=2;i<n;i++)
{
if(s[i]!='0') dp[i]+=dp[i-1]; //如果自己课单独解码,则方法总数为以上一个结尾的解码方法数
int tmp=(s[i-1]-'0')*10+s[i]-'0';
if(tmp>=10 && tmp<=26)
{
dp[i]+=dp[i-2];//如果联合解码成功,则方法总数为以上上一个结尾的解码方法数
}
}
return dp[n-1];
}
};