# 遞精喔喔喔喔喔喔 --- [TOC] ###### tags: `110程式設計一` --- ## 一般遞迴 code is here: ```c= int climbStairs(int n){ if(n < 4) return n; else return climbStairs(n - 1) + climbStairs(n - 2); } ``` 我們先發現這題跟費氏數列一樣 --- ### Submission in Leetcode: ![](https://i.imgur.com/75BkhTX.png) --- ## 遞迴記憶 code is here: ```c= int cache[46] = {0}; int climbStairs(int n){ if(n < 4) return n; if (cache[n] > 0) return cache[n]; else cache[n] = climbStairs(n - 1) + climbStairs(n - 2); return cache[n]; } ``` --- ### Submission in Leetcode: ![](https://i.imgur.com/gohcUsq.png) ## DP(動態規劃): code is here: ```c= int climbStairs(int n){ if(n < 4) return n; int prv = 1; int after = 2; int res; for(int i = 3; i <= n ;i++){ res = prv + after; prv = after; after = res; } return res; } ``` --- ### Submission in Leetcode: ![](https://i.imgur.com/6KI5v2T.png) 稍微優化一下 --- ## DP優化 code is here: ```c= int climbStairs(int n){ if(n < 4) return n; int prv = 2; int after = 3; int res; for(int i = 4; i <= n ;i++){ res = prv + after; prv = after; after = res; } return res; } ``` --- ### Submission in Leetcode: ![](https://i.imgur.com/94b3XhB.png)