动态规划:从入门到入土系列(二)

🎈个人主页:🎈 :✨✨✨初阶牛✨✨✨
🐻推荐专栏1: 🍔🍟🌯C语言初阶
🐻推荐专栏2: 🍔🍟🌯C语言进阶
🔑个人信条: 🌵知行合一

前言

一、使用最小花费爬楼梯

题目来源于:力扣
题目链接:传送门

(1) 题目描述

给你一个整数数组 cost ，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用，即可选择向上爬一个或者两个台阶。

你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。(表示开始费用为0)

目的:请你计算并返回达到楼梯顶部的最低花费。

示例:

示例 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 。

(2)解题思路

对于动态规划类的题目,都是有固定格式的,

1. 确定状态表示.
2. 创建dp表,
3. 填写dp表(根据状态转移方程)
4. 细节处理,是否越界?初始化等问题.
5. 确认返回值.

状态表示

状态表示:

dp[n]表示到达,第下标为n阶楼梯的最小花费.

状态转移方程:

由于支付费用可以向前走一个或者两个台阶,那么到达当前台阶(n)有两种情况.

情况1:从第n-2阶,走两步到达.
情况2: 从第n-1阶走一步到达.

细节处理:

由于状态转移方程可能会发生越界访问,所以,需要对dp[0]和dp[1]处理.

还记得题干说的吗?可以从第一个台阶或者第二个台阶起步.
意味着,到达第一阶楼梯和第二阶楼梯的花费都是0.

返回值确认:

(3)代码展示:

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        int n=cost.size();			//获取cost表的长度
        vector<int> dp(n+1);      //创建dp表

        //初始化
        dp[0]=0;
        dp[1]=0;
        //填表
        for(int i=2;i<=n;i++)
        {
        //根据状态转移方程
            dp[i]=min(dp[i-2]+cost[i-2],dp[i-1]+cost[i-1]);
        }
        //返回值,此处楼顶应该是dp[n]
        return dp[n];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

二、解码方法:

题目来源于:力扣
题目链接:传送门

(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 ，请计算并返回 解码 方法的 总数 。

示例

示例 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 <= s.length <= 100
s 只包含数字，并且可能包含前导零。

(2)解题思路:

状态表示

dp[n]表示到达下标为n处,解码 方法的 总数.

状态转移方程:

细节处理:

要处理边界问题,状态转移方程中至少要确定前两个位置才能计算下一个.

dp[0]:单独编码,
成功:dp[0]=1;
失败: dp[0]=0;

dp[1]:单独编码:
成功:dp[1-1]=dp[0]
失败:方法+0

dp[0]与dp[1]:联合编码:
成功: 方法+1
失败: 方法+0

返回值确认:

dp[n-1]表示到达下标为n-1处,解码 方法的 总数,也就是到最后一个字母的解码总数.

(3)代码展示:

class Solution {
public:
    int numDecodings(string s) {
        int n=s.size();		//获取字符串s的长度
        vector<int> dp(n); //创建一个n大小空间的vector(所有元素默认初始化为了0)
        
        //初始化
        //if(s[0]-'0'>0   &&  s[0]-'0'<=9) dp[0]=1;	写法1
        //写法2
        if(s[0]!='0')dp[0]=1;       //因为该字符串只会出现数字,所以非0就是解码成功

        if(n==1) return dp[0];  //特殊情况,s的长度为1

        if(s[1]!='0')    dp[1]=dp[0];        //dp[1]单独编码成功
        //联合编码
       int tmp=(s[0]-'0')*10+s[1]-'0';
        if(tmp>=10 &&  tmp<=26)
        {
            dp[1]+=1;
        }
        
        //填表
       for(int i=2;i<n;i++)
        {
            if(s[i]!='0') dp[i]+=dp[i-1];		//如果自己课单独解码,则方法总数为以上一个结尾的解码方法数
            int tmp=(s[i-1]-'0')*10+s[i]-'0';
            if(tmp>=10 &&  tmp<=26)
            {
                dp[i]+=dp[i-2];//如果联合解码成功,则方法总数为以上上一个结尾的解码方法数
            } 
        }
        return dp[n-1];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34