Re: [閒聊] 每日LeetCode已回收
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
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 36.231.14.41 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1670807109.A.FB0.html
推
12/12 09:08,
3年前
, 1F
12/12 09:08, 1F
推
12/12 09:17,
3年前
, 2F
12/12 09:17, 2F
推
12/12 09:17,
3年前
, 3F
12/12 09:17, 3F
推
12/12 09:29,
3年前
, 4F
12/12 09:29, 4F
→
12/12 09:30,
3年前
, 5F
12/12 09:30, 5F
討論串 (同標題文章)
完整討論串 (本文為第 134 之 719 篇)：