【算法挨揍日记】day18——746. 使用最小花费爬楼梯、91. 解码方法

川长思鸟来 2024-02-21 12:28 30阅读 0赞

### 746. 使用最小花费爬楼梯 ###

[746. 使用最小花费爬楼梯][746.]

### 题目描述: ###

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

你可以选择从下标为 `0` 或下标为 `1` 的台阶开始爬楼梯。

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

![b9d0ad6bc53b42ce8d2816b0f3e974a9.png][]

### 解题思路： ###

> 状态描述：我们可以直接将dp【i】 代表到达第i个台阶的最小费用
> 
>     cost = [1,100,1,1,1,100,1,1,100,1]
> 
> 以这个示例为例
> 
> ![ce71a9edb9704f65b12098280b75dad8.png][]
> 
> 状态转移方程：
> 
>  *  **dp\[i\]=min(dp\[i-1\]+cost\[i-1\],dp\[i-2\]+cost\[i-2\])**
> 
> 初始化:dp【0】=0，dp【1】=0；
> 
> 填表顺序：从左到右
> 
> 返回值：dp【n】

### 解题代码： ###

class Solution {
    public:
        int minCostClimbingStairs(vector<int>& cost) {
            int n=cost.size();
            vector<int>dp(n+1);
            dp[0]=0;dp[1]=0;
            for(int i=2;i<n+1;i++)
                dp[i]=min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]);
            return dp[n];
        }
    };

--------------------

### 91. 解码方法 ###

[91. 解码方法][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 位** 的整数。

### 解题思路： ###

> 本题的状态表示是通过经验+题目要求得出的
> 
> 状态表示：dp\[i\]代表以i位置结尾的所有解码方法总和
> 
> 状态转移方程：
> 
> ![f79931ff448e4cc2b13d69e6f07c68ec.png][]
> 
> 我们就观察以i位置结尾的数字串，此时有两种情况：
> 
>  *  s\[i\]单独解码
>  *  s\[i\]和s\[i-1\]一起解码
> 
> 先说s【i】单独解码的情况，当解码成功时，也就是s【i】代表的数字属于【1，9】，则dp【i】+=dp【i-1】，失败的话就是0了
> 
> 再来就是 s\[i\]和s\[i-1\]一起解码 的情况：当解码成功也就是这两个数字属于【10,26】,则dp【i】+=dp【i-2】，失败也是0
> 
> 初始化：dp【0】当s【0】属于1-9，dp【0】=1，s【0】=0的话dp【0】=0
> 
> dp【1】的话，此时就有两个数字，就分为两种情况，两个数字分开单独解码和两个数字一起解码，单独解码的话s【1】代表的数字属于【1，9】，dp【1】++，两个数字一起解码的话，当解码成功也就是这两个数字属于【10,26】,则dp【1】++
> 
> 填表顺序：从左导游
> 
> 返回值;dp\[n-1\]

### 解题代码： ###

class Solution {
    public:
        int numDecodings(string s) {
            int n = s.size();
            vector<int>dp(n + 1, 0);
            //初始化
            if (s[0] >= '1' && s[0] <= '9')dp[0] = 1;
            else dp[0] = 0;
            if (n == 1)return dp[0];
    
            if (dp[0] && s[1] - '0')dp[1]++;
            int num = (s[0] - '0') * 10 + (s[1] - '0');
            if (num >= 10 && num <= 26)dp[1]++;
    
            for (int i = 2; i < n; i++)
            {
                if (s[i] >= '1' && s[i] <= '9')dp[i] += dp[i - 1];
                num = (s[i - 1] - '0') * 10 + (s[i] - '0');
                if (num >= 10 && num <= 26)dp[i] += dp[i - 2];
            }
            return dp[n - 1];
        }
    };

### 处理边界问题及初始化问题的的技巧： ###

我们可以给dp数组多开一个位置，也就是开n+1个空间，使整个数组向右移动一位

这样我们原本的dp【1】也可以移到循环中进行计算了！！！

![cffc1b4dc38c416a9c5086ad24d6e750.png][]

这里的0,1,2等都是下标

因此我们多出来一个位置0号下标的值是多少呢？

因为我们后面要计算dp【2】也就是原本的dp【1】的时候会运用到dp【i-2】和dp【i-1】

因为dp【i-1】不会出错，所以我们只需要注意dp【i-2】的正确性

当dp【2】时，也就是两位数字的解码方案数，当我们运用到dp【i-2】的时候，这个是两位数字一起解码，因此dp【i】+=dp【i-2】如果dp【0】为0，即使解码成功也等于没有解码成功，因此这里dp【0】要为1

### 优化后的代码： ###

class Solution {
    public:
        int numDecodings(string s) {
            int n=s.size();
            vector<int>dp(n+1);
            dp[0]=1;
            //初始化
            if(s[0]>='1'&&s[0]<='9')dp[1]=1;
            else dp[1]=0;
            if(n==1)return dp[1];
    
            /*if(dp[0]&&s[1]-'0')dp[1]++;
            int num=(s[0]-'0')*10+(s[1]-'0');
            if(num>=10&&num<=26)dp[1]++;*/
            
            for(int i=2;i<=n;i++)
            {
                if(s[i-1]>='1'&&s[i-1]<='9')dp[i]+=dp[i-1];
                int num=(s[i-2]-'0')*10+(s[i-1]-'0');
                if(num>=10&&num<=26)dp[i]+=dp[i-2];
            }
            return dp[n];
        }
    };

###  ###

[746.]: https://leetcode.cn/problems/min-cost-climbing-stairs/
[b9d0ad6bc53b42ce8d2816b0f3e974a9.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/21/9c999c290678469b8965015146e8829f.png
[ce71a9edb9704f65b12098280b75dad8.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/21/0a09723f3e9f4c1186c5453a9d9ce5a1.png
[91.]: https://leetcode.cn/problems/decode-ways/
[f79931ff448e4cc2b13d69e6f07c68ec.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/21/399acca60e0542fa9c9e55821693bc7b.png
[cffc1b4dc38c416a9c5086ad24d6e750.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/21/4ae821612ced454d921c5bbb52bfe049.png