【动态规划刷题 2】使⽤最⼩花费爬楼梯 && 解码⽅法-Toy模板网

这篇具有很好参考价值的文章主要介绍了【动态规划刷题 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 阶位置，只有两种情况：

从 i-1 阶爬一阶楼梯到 i;
从 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];
    }

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

解码方法

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 的位置进行分析，有两种情况：

i位置是的数字在 1~9 之间，能单独表示一个字母
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的值初始化。

当s[0]不为‘0’ 时，dp[0]=1; 否则，dp[0]=0;
当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];
}