推 sustainer123: 大師 12/12 09:08
推 pandix: 大師 12/12 09:17
推 DDFox: 大師 12/12 09:17
推 louiss72: 費氏遞迴也能做吧 只是不知道複雜度多少 12/12 09:29
→ louiss72: 啊 這就是 我只看到題目 12/12 09:30
70. Climbing Stairs
龍大要爬樓梯，他每次可以選擇走一階或走兩階，求出爬到第n階共有幾種走法。
Example :
Input: n = 3
Output: 3
Explanation: There are three ways to climb to the top.
1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 step
思路：
1.經典的dp題，到第i階的可能走法為從i-1位置走一步加上從i-2位置走兩步，
狀態轉移方程為 dp[i] = dp[i - 1] + dp[i - 2]。
2.因為我們只要知道前兩階共有幾種走法，所以dp只需要維護大小為2的陣列即可，
空間複雜度O(n) ==> O(1)
Java Code：
---------------------------------
class Solution {
public int climbStairs(int n) {
int[] dp = {1, 1};
for (int i = 1; i < n; i++) {
int one = dp[0];
dp[0] = dp[1];
dp[1] = one + dp[0];
}
return dp[1];
}
}
---------------------------------
https://i.imgur.com/acHi4CL.png
--
https://i.imgur.com/sjdGOE3.jpg
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 36.231.14.41 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1670807109.A.FB0.html