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

简介: 【动态规划刷题 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];
}

相关文章
代码随想录Day27贪心02 下 LeetCodeT45 跳跃游戏II
代码随想录Day27贪心02 下 LeetCodeT45 跳跃游戏II
35 0
|
6月前
|
存储 SQL 算法
优化解码方法:记忆化搜索和空间优化动态规划的实用指南 【LeetCode 题目 91】
优化解码方法:记忆化搜索和空间优化动态规划的实用指南 【LeetCode 题目 91】
|
7月前
【错题集-编程题】买卖股票的最好时机(一)(贪心 + 动态规划)
【错题集-编程题】买卖股票的最好时机(一)(贪心 + 动态规划)
|
7月前
|
存储 算法
从动态规划到贪心算法:最长递增子序列问题的方法全解析
从动态规划到贪心算法:最长递增子序列问题的方法全解析
54 1
|
7月前
|
Java Python
牛客笔试-变换次数
牛客笔试-变换次数
44 0
|
7月前
|
算法 测试技术 C++
【状态压缩】【动态规划】【C++算法】691贴纸拼词
【状态压缩】【动态规划】【C++算法】691贴纸拼词
JAVA实现开根号的两种方式:二分法以及牛顿迭代法
JAVA实现开根号的两种方式:二分法以及牛顿迭代法
281 0
|
机器学习/深度学习 算法 JavaScript
代码随想录训练营day31| 455.分发饼干 376. 摆动序列 53. 最大子序和
代码随想录训练营day31| 455.分发饼干 376. 摆动序列 53. 最大子序和
|
算法
LeetCode 周赛 344(2023/05/07)手写递归函数的固定套路
大家好,我是小彭。 今天下午有力扣杯战队赛,不知道官方是不是故意调低早上周赛难度给选手们练练手。
122 0
|
存储 算法 C语言
动态规划算法解决背包问题,算法分析与C语言代码实现,时间效率解析
动态规划算法解决背包问题,算法分析与C语言代码实现,时间效率解析
203 0