免备案做网站可以盈利吗,wordpress页面发布失败为什么,dedecms 安防监控行业网站模板,新公司注册工商核名系统文章目录 使用最小花费爬楼梯解码方法 使用最小花费爬楼梯
【题目描述】 给你一个整数数组 cost #xff0c;其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用#xff0c;即可选择向上爬一个或者两个台阶。
你可以选择从下标为 0 或下标为 1 的台阶… 文章目录 使用最小花费爬楼梯解码方法 使用最小花费爬楼梯
【题目描述】 给你一个整数数组 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 10000 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(vectorint cost) {//1.创建dp表int n cost.size();vectorint dp(n1);//2.初始化dp[0] dp[1] 0;if(n 2) return 0;//3.填表for(int i 2;in1;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(vectorint cost) {//1.创建dp表int n cost.size();vectorint dp(n);//2.初始化dp[n-2] cost[n-2];dp[n-1] cost[n-1];//3.填表for(int i n-3;i0;i--){dp[i] min(dp[i1]cost[i],dp[i2]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 100s 只包含数字并且可能包含前导零。
【解题思路】 定义一个数组 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();vectorint dp(n);// 处理第一个字符dp[0] s[0] ! 0;if(n1)return dp[0];// 处理前两个字符if(s[0]!0 s[1]!0)dp[1];int t (s[0]-0)*10 (s[1]-0);if(t10 t26)dp[1];// 从第三个字符开始遍历for(int i 2;in;i){// 将当前字符作为单独的一个字母解码if(s[i] ! 0)dp[i] dp[i-1];// 将当前字符与前一个字符一起解码t (s[i-1]-0)*10 (s[i]-0);if(t10 t26)dp[i] dp[i-2];}return dp[n-1];}
};
