LeetCode刷题笔记-动态规划-day2

小咪咪 2023-10-01 17:19 19阅读 0赞

#### 文章目录 ####

*  LeetCode刷题笔记-动态规划-day2
 *   *  70. 爬楼梯
     *   *  1.题目
         *  2.解题思路
         *  3.代码
     *  746. 使用最小花费爬楼梯
     *   *  1.题目
         *  2.解题思路
         *  3.代码

## LeetCode刷题笔记-动态规划-day2 ##

### 70. 爬楼梯 ###

#### 1.题目 ####

> 原题链接：[70. 爬楼梯][70.]

![image-20220206085509252][]

#### 2.解题思路 ####

算法：递推

定义数组`f[i]`表示到第`i`级台阶的总方案数，走到第`i`级台阶的前一步可能走了`1`级台阶，也可能走了`2`级台阶，所以这里可以得到递推式：

f[i]=f[i-1]+f[i-2];

最终递推一遍即可。

#### 3.代码 ####

class Solution {
        
    public:
        int climbStairs(int n) {
        
            vector<int> f(n+1);
            f[0]=1,f[1]=1;
            for(int i=2;i<=n;i++) 
                f[i]=f[i-1]+f[i-2];
            return f[n];
        }
    };

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

#### 1.题目 ####

> 原题链接：[746. 使用最小花费爬楼梯][746.]

![image-20220206085528836][]

![image-20220206085539756][]

#### 2.解题思路 ####

算法：递推

由题意可知，到达第`i`级台阶需要的总费用等于第`i`级台阶自身需要的费用加上经过前面台阶的总费用，而每次可以选择向上爬一个或者两个台阶。可以得出递推式：

f[i]=c[i]+min(f[i-1],f[i-2]);

初始化： `f[0]=c[0],f[1]=c[1];`

最终楼梯顶部为`n`号台阶，我们只需要算出第`n-1`和`n-2`级台阶的值，取两者之间最小值即可。

#### 3.代码 ####

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

![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBATEwuTEVCUk9O_size_20_color_FFFFFF_t_70_g_se_x_16]

[70.]: https://leetcode-cn.com/problems/climbing-stairs/
[image-20220206085509252]: https://img-blog.csdnimg.cn/img_convert/11d9e72f2dd7f8bc36861eb41b45d564.png
[746.]: https://leetcode-cn.com/problems/min-cost-climbing-stairs/
[image-20220206085528836]: https://img-blog.csdnimg.cn/img_convert/fe73b418757587ce907b7c982d89470e.png
[image-20220206085539756]: https://img-blog.csdnimg.cn/img_convert/6804e8a84d0b5ec3c84ae78f7e67bea7.png
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBATEwuTEVCUk9O_size_20_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/d6bab70031b546af992594380d1ead6b.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBATEwuTEVCUk9O,size_20,color_FFFFFF,t_70,g_se,x_16