使用最小花费爬楼梯
【题目描述】
给你一个整数数组 cost
,其中 cost[i]
是从楼梯第 i
个台阶向上爬需要支付的费用。一旦你支付此费用,即可选择向上爬一个或者两个台阶。
你可以选择从下标为 0
或下标为 1
的台阶开始爬楼梯。
请你计算并返回达到楼梯顶部的最低花费。
【输入样例】
cost = [10,15,20]
cost = [1,100,1,1,1,100,1,1,100,1]
【输出样例】
15
6
【数据规模与约定】
2 <= cost.length <= 1000
0 <= cost[i] <= 999
【解题思路】
定义一个数组 dp,其中 dp[i] 表示达到第 i 个台阶的最低花费。
对于第 i 个台阶,我们有两种选择:
- 从第 i-1 个台阶向上爬一个台阶,花费为 dp[i-1] + cost[i-1]。
- 从第 i-2 个台阶向上爬两个台阶,花费为 dp[i-2] + cost[i-2]。
我们选择这两种方案中花费较小的那个,即 dpi = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2])。
最终,dp[n] 就是达到楼梯顶部的最低花费。
【C++程序代码】
解法一:
class Solution {
public:
int minCostClimbingStairs(vector<int>& cost) {
//1.创建dp表
int n = cost.size();
vector<int> dp(n+1);
//2.初始化
dp[0] = dp[1] = 0;
if(n <2) return 0;
//3.填表
for(int i = 2;i<n+1;i++)
{
dp[i] = min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]);
}
//4.返回值
return dp[n];
}
};
解法二:
class Solution {
public:
int minCostClimbingStairs(vector<int>& cost) {
//1.创建dp表
int n = cost.size();
vector<int> dp(n);
//2.初始化
dp[n-2] = cost[n-2];
dp[n-1] = cost[n-1];
//3.填表
for(int i = n-3;i>=0;i--)
{
dp[i] = min(dp[i+1]+cost[i],dp[i+2]+cost[i]);
}
//4.返回值
return min(dp[0],dp[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
,请计算并返回 解码 方法的 总数 。
题目数据保证答案肯定是一个 32 位 的整数。
【输入样例】
s = "12"
s = "06"
【输出样例】
2
0
【数据规模与约定】
1 <= s.length <= 100
s
只包含数字,并且可能包含前导零。
【解题思路】
定义一个数组 dp,其中 dp[i] 表示前 i 个字符可以解码的方法总数。
对于第 i 个字符,我们有两种选择:
- 将其作为单独的一个字母进行解码,前提是第 i 个字符不为 ‘0’。在这种情况下,我们可以将前 i-1 个字符解码的方法数加到 dp[i]上,即 dp[i] += dp[i-1]。
- 将其与前一个字符一起解码,形成一个两位数。前提是第 i-1 个字符不为 ‘0’,且与第 i 个字符组成的两位数在 10 到 26 之间。在这种情况下,我们可以将前 i-2 个字符解码的方法数加到 dpi 上,即 dp[i] += dp[i-2]。
最终,dp[n-1] 就是整个字符串的解码方法总数。
【C++程序代码】
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]++;
int t = (s[0]-'0')*10 + (s[1]-'0');
if(t>=10 && t<=26)
dp[1]++;
// 从第三个字符开始遍历
for(int i = 2;i<n;i++)
{
// 将当前字符作为单独的一个字母解码
if(s[i] != '0')
dp[i] += dp[i-1];
// 将当前字符与前一个字符一起解码
t = (s[i-1]-'0')*10 + (s[i]-'0');
if(t>=10 && t<=26)
dp[i] += dp[i-2];
}
return dp[n-1];
}
};