【动态规划刷题 2】使⽤最⼩花费爬楼梯 解码⽅法

使⽤最⼩花费爬楼梯

746 . 使用最小花费爬楼梯
链接: 746 . 使用最小花费爬楼梯

给你一个整数数组 cost ，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用，即可选择向上爬一个或者两个台阶。
你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。
请你计算并返回达到楼梯顶部的最低花费。

示例 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 。

1.状态表示

dp[i] 表示的是爬到第 i 阶楼梯时的最低花费。

2.状态转移方程

动态规划题，我们需要学会依靠经验和题目解析去猜测他们的状态转移方程。
爬到第i 阶位置，只有两种情况：

1. 从 i-1 阶 爬一阶楼梯到 i;
2. 从 i-2 阶 爬二阶楼梯到 i;

所以dp[i] 的值只需要 去其中的较小值即可,

dp[i]=min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]);

3. 初始化

从我们的递推公式可以看出， dp[i] 在 i = 0 以及 i = 1 的时候是没有办法进⾏推导的，因为dp[i-2] 或 dp[i-1] 不是⼀个有效的数据。

因此我们需要在填表之前，将0, 1的值初始化。题⽬中已经告诉我们
dp[0] = dp[1]=0

4. 填表顺序
按照数组下标的顺序，从左往右。

5. 返回值
应该返回 dp[n] 的值。

代码：

  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-1]+cost[i-1],dp[i-2]+cost[i-2]);}return dp[n];}

解码方法

91 . 解码方法
一条包含字母 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 ，请计算并返回 解码 方法的 总数 。
题目数据保证答案肯定是一个 32 位 的整数。

示例 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.状态表示

dp[i] 表示的是以第i位置为结尾时的解码方法数。

2.状态转移方程

动态规划题，我们需要学会依靠经验和题目解析去猜测他们的状态转移方程。
以 i-1 的位置进行分析，有两种情况：

1. i位置是的数字在 1~9 之间，能单独表示一个字母
2. i和i-1 位置的数字可以组成一个在 10 ~ 26 之间的一个字母

所以
i. 当 s[i] 上的数在 [1, 9] 区间上时： dp[i] += dp[i - 1] ；
ii. 当 s[i - 1] 与 s[i] 上的数结合后，在 [10, 26] 之间的时候： dp[i] +=dp[i - 2] ；

3. 初始化

从我们的递推公式可以看出， dp[i] 在 i = 0 以及 i = 1 的时候是没有办法进⾏推导的，因为dp[i-2] 或 dp[i-1] 不是⼀个有效的数据。

因此我们需要在填表之前，将0, 1的值初始化。

1. 当s[0]不为‘0’ 时，dp[0]=1; 否则，dp[0]=0;
2. 当s[1]!=‘0’ 时，dp[1]+=1; 当 s[0] 与 s[1] 上的数结合后，在 [10, 26] 之间的时,dp[1]+=1;

4. 填表顺序
按照数组下标的顺序，从左往右。

5. 返回值
应该返回 dp[n-1] 的值。

代码

    int numDecodings(string s) {//动态规划//创建dp[]数组//初始化//填表//返回值int n=s.size();vector<int> dp(n);//初始化if(s[0]=='0') return 0;dp[0]=1;if(n==1) return dp[0];if(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];
}