蓝桥杯刷题-day5-动态规划

使用最小花费爬楼梯

【题目描述】
给你一个整数数组 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 个台阶，我们有两种选择：

1. 从第 i-1 个台阶向上爬一个台阶，花费为 dp[i-1] + cost[i-1]。
2. 从第 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 个字符，我们有两种选择：

1. 将其作为单独的一个字母进行解码，前提是第 i 个字符不为 ‘0’。在这种情况下，我们可以将前 i-1 个字符解码的方法数加到 dp[i]上，即 dp[i] += dp[i-1]。
2. 将其与前一个字符一起解码，形成一个两位数。前提是第 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];
    }
};