动态规划练习（3）爬楼梯-LeetCde

快来打我* 2023-09-28 22:46 16阅读 0赞

三字诀：**定—方—始**

**定：**定义数组含义，**确定最后一步完成情况**（难度：⭐⭐⭐⭐⭐），肯定子问题成立

**方：写表达式**（就那个核心方程，难度：⭐⭐⭐）

**始：**给出初始条件

总之一句话：用**数组**去完成**最后一步**得出**方程式，**给出**初始**累代码

## 问题描述： ##

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

示例 1：

输入：n = 2  
输出：2  
解释：有两种方法可以爬到楼顶。  
1. 1 阶 + 1 阶  
2. 2 阶  
示例 2：

输入：n = 3  
输出：3  
解释：有三种方法可以爬到楼顶。  
1. 1 阶 + 1 阶 + 1 阶  
2. 1 阶 + 2 阶  
3. 2 阶 + 1 阶

提示：

1 <= n <= 45

来源：力扣（LeetCode）  
链接：https://leetcode.cn/problems/climbing-stairs

**分析：**

**定：** 设steps\[i\]表示到第i个台阶去的不同方法数总和。

最后一步：1、从n-1处上一个台阶到达楼顶，有steps\[n-1\]种

2、从n-2处上两个台阶到达楼顶，有steps\[n-2\]种

所以最后一步：steps\[n\]=steps\[n-1\]+steps\[n-2\]

把n换i不就是子问题了嘛，完全肯定

**方：**steps\[i\]=steps\[i-1\]+steps\[i-2\]

**始：**当i<=2时，方程不成立，所以steps1\]和steps\[2\]得给初始值，即steps\[1\]=1和steps\[2\]=2

累代码：

class Solution {
    public:
        int climbStairs(int n) {
            int steps[46];
            steps[1]=1;
            steps[2]=2;
            if(n>2)
                for(int i=3;i<=n;i++)
                    steps[i]=steps[i-1]+steps[i-2];
            return steps[n];
        }
    };

测试结果：

![8108d123aae34b2ba53f4c9124a3f33f.png][]

[8108d123aae34b2ba53f4c9124a3f33f.png]: https://img-blog.csdnimg.cn/8108d123aae34b2ba53f4c9124a3f33f.png

发表评论取消回复

表情：

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

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

相关阅读

相关 LeetCode_动态规划_简单_70.爬楼梯

目录 1.题目 2.思路 3.代码实现（Java） 1.题目假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台

绝地灬酷狼/ 2023年10月06日 19:17/ 0 赞/ 99 阅读

相关动态规划之爬楼梯

[70. 爬楼梯][70.] 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

迷南。/ 2023年09月30日 21:14/ 0 赞/ 100 阅读

相关动态规划练习（3）爬楼梯-LeetCde

三字诀：定—方—始定：定义数组含义，确定最后一步完成情况（难度：⭐⭐⭐⭐⭐），肯定子问题成立方：写表达式（就那个核心方程，难度：⭐⭐⭐）始：给出初始条件总之一句

快来打我*/ 2023年09月28日 22:46/ 0 赞/ 17 阅读

相关算法-动态规划-爬楼梯

算法-动态规划-爬楼梯 1 概述 1.1 题目出处 https://leetcode-cn.com/problems/climbing-stairs 1.

男娘i/ 2023年07月19日 12:25/ 0 赞/ 42 阅读

相关利用动态规划求解爬楼梯问题

题目描述：假设你正在爬楼梯，需要n阶才能到达楼顶。每次可以爬1或2阶，你有多少种不同的方法可以爬到楼顶呢？其中n是一个正整数。思路和算法：利用动态规划，用f

约定不等于承诺〃/ 2022年12月28日 05:30/ 0 赞/ 246 阅读

相关算法题目——爬楼梯(动态规划)

题目链接：[70.爬楼梯][70.] 类似题目：[1646.获取生成数组中最大值][1646.] ![在这里插入图片描述][watermark_type_ZHJvaWRz

╰+哭是因爲堅強的太久メ/ 2022年09月14日 11:14/ 0 赞/ 312 阅读

相关动态规划--爬楼梯

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

心已赠人/ 2022年05月23日 07:47/ 0 赞/ 311 阅读

相关动态规划--最小代价爬楼梯

1、题目： On a staircase, the `i`\-th step has some non-negative cost `cost[i]` assigned (0

Myth丶恋晨/ 2022年05月23日 07:46/ 0 赞/ 293 阅读

相关 [算法提高] 动态规划爬楼梯

\[问题背景\] 来源：LeetCode(力扣) 编号：[70. 爬楼梯][70.] 内容：假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或

喜欢ヅ旅行/ 2022年03月06日 04:03/ 0 赞/ 312 阅读

相关 [动态规划] 70. 爬楼梯

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

约定不等于承诺〃/ 2021年12月09日 00:19/ 0 赞/ 337 阅读