首页 > 代码库 > [LeetCode] Climbing Stairs （Sequence DP）
[LeetCode] Climbing Stairs （Sequence DP）
Climbing Stairs
https://oj.leetcode.com/problems/climbing-stairs/
You are climbing a stair case. It takes n steps to reach to the top.
Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?
这题比较简单，可以使用动态规划来求解。请看以下分析：
State：f[i] 表示从起点出发达到第 i 个位置的方案总数
Function：由于第 i 个位置可以由第 i – 2 个位置走两步或者由第 i – 1 个位置走一步而到达，因此有以下状态转移方程：
f[i] = f[i-1] + f[i-2]
Initialize：1. 从起点走到第一个位置，显然只有走 1 步到达这一种方案。
2. 从起点走到第二个位置，有两种方案：直接走 2 步或者每次走 1 步，走 2 次。因此，初始化状态如下：
f[0] = 1
f[1] = 2
注意：数组下标从0开始。
Answer：f[n - 1] 。
下面为 AC 的代码：
/** * Author : Zhou J * Email : zhoujx0219@163.com */class Solution {public: int climbStairs(int n) { if (n == 0) { return 0; } // State: 从起点走到第 i 个位置的方案总数 int sum[n]; // initialize sum[0] = 1; if (n >= 2) { sum[1] = 2; } // switch the state for (size_t ix = 2; ix < n; ++ix) { sum[ix] = sum[ix - 1] + sum[ix - 2]; } return sum[n - 1]; }};
Optimize
当然，此处并不需要使用一个 n 维的数组来存放 State ，观察状态转移方程就可以知道，此处只需要两个变量来存放状态即可。因此下面的代码对空间做了进一步的优化：
/** * Author : Zhou J * Email : zhoujx0219@163.com */class Solution {public: int climbStairs(int n) { if (n <= 2) { return n; } size_t now;
size_t lastlast = 2; // f[1] size_t last = 1; // f[0] // switch the state for (size_t ix = 2; ix < n; ++ix) { now = lastlast + last; last = lastlast; lastlast = now; } return now; }};
[LeetCode] Climbing Stairs （Sequence DP）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。