LeetCode 70. Climbing Stairs (简单动归)

客官°小女子只卖身不卖艺 2024-04-17 23:42 43阅读 0赞

题目描述：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjUyNjE5_size_16_color_FFFFFF_t_70][]

这道题应该属于比较简单的动归了，一眼扫过去差不多能出公式：

可以想象当前步只能由上一步和上上步两个途径加起来，dp数组存储到当前步有多少条路  
那么 i 的子问题就是 i-1 和 i-2  
dp\[i\] = dp\[i-1\] + dp\[i-2\] if((i-2) >= 0);  
dp\[i\] = dp\[i-1\] if(i == 1)  
dp\[i\] = 1 if(i == 0)

class Solution {
    public:
        int climbStairs(int n) {
            //这个的话，其实算是简单DP吧
            //可以想象当前步只能由上一步和上上步两个途径加起来，dp数组存储到当前步有多少条路
            //那么 i 的子问题就是 i-1 和 i-2
            //dp[i] = dp[i-1] + dp[i-2] if((i-2) >= 0);
            //dp[i] = dp[i-1] if(i == 1)
            //dp[i] = 1 if(i == 0)
            int dp[n + 5];
            dp[0] = 1;
            dp[1] = 1;
            for(int i = 2; i <= n; i++){
                dp[i] = dp[i-1] + dp[i-2];
            }
            return dp[n];
        }
    };

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjUyNjE5_size_16_color_FFFFFF_t_70 1][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjUyNjE5_size_16_color_FFFFFF_t_70]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/17/2ccef14d0e6e45c5813dd7b594a8e8de.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjUyNjE5_size_16_color_FFFFFF_t_70 1]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/17/75a7c2e752d94c739581968c12a59f4a.png

发表评论取消回复

表情：

评论列表（有 0 条评论，43人围观）

还没有评论，来说两句吧...

相关阅读

相关 LeetCode 70. Climbing Stairs (简单动归)

目描述： ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV...

客官°小女子只卖身不卖艺/ 2024年04月17日 23:42/ 0 赞/ 44 阅读

相关 LeetCode - Easy - 70. Climbing Stairs

Topic Dynamic Programming Description [https://leetcode.com/problems/climbing-sta

深藏阁楼爱情的钟/ 2022年12月28日 00:40/ 0 赞/ 131 阅读

相关 LeetCode70——Climbing Stairs

LeetCode70——Climbing Stairs 题意：爬楼梯你可以爬一步或者两步，求你到终点时有多少种可能。首先假设终点是3 则你可以： 1.先

喜欢ヅ旅行/ 2022年08月09日 17:47/ 0 赞/ 145 阅读

相关【LeetCode】70. Climbing Stairs

70. Climbing Stairs You are climbing a stair case. It takes n steps to reach to the

柔光的暖阳◎/ 2022年07月26日 08:35/ 0 赞/ 158 阅读

相关 [leetcode]: 70. Climbing Stairs

1.题目 You are climbing a stair case. It takes n steps to reach to the top. Each time

拼搏现实的明天。/ 2022年06月15日 02:11/ 0 赞/ 141 阅读

相关【LeetCode】70. Climbing Stairs

> You are climbing a stair case. It takes n steps to reach to the top. > > Each time yo

阳光穿透心脏的1/2处/ 2022年05月21日 07:20/ 0 赞/ 133 阅读

相关 70. Climbing Stairs

You are climbing a stair case. It takes n steps to reach to the top. Each time you can

浅浅的花香味﹌/ 2022年05月16日 15:56/ 0 赞/ 126 阅读

相关 LeetCode 70.Climbing Stairs (爬楼梯)

题目描述：假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？注意：给定 n 是一个正整数。示例

迷南。/ 2022年05月10日 05:50/ 0 赞/ 172 阅读

相关【Leetcode】70. Climbing Stairs（动态规划）

You are climbing a stair case. It takes n steps to reach to the top. Each time you can

野性酷女/ 2022年04月23日 15:18/ 0 赞/ 160 阅读

相关【LeetCode】70. Climbing Stairs

Introduction You are climbing a stair case. It takes n steps to reach to the top. E

深藏阁楼爱情的钟/ 2022年03月15日 09:16/ 0 赞/ 161 阅读