題目鏈接：https://leetcode-cn.com/problems/climbing-stairs/

之前在遞歸中講過這個(gè)問題，現(xiàn)在用動(dòng)態(tài)規(guī)劃求解。

假設(shè)你正在爬樓梯。需要 n 階你才能到達(dá)樓頂。
每次你可以爬 1 或 2 個(gè)臺(tái)階。你有多少種不同的方法可以爬到樓頂呢？
注意：給定 n 是一個(gè)正整數(shù)。

用dp[i] 表示到達(dá)第i個(gè)臺(tái)階的走法，那么到達(dá)第n個(gè)臺(tái)階的這個(gè)狀態(tài)的走法，只跟n-1和n-2的狀態(tài)有關(guān)（走1步或2步到n）
狀態(tài)方程為 dp[n] = dp[n-1] + dp[n-2]

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

對(duì)上面程序進(jìn)行狀態(tài)壓縮，前面用不到的狀態(tài)不保留

class Solution { public:int climbStairs(int n) {if(n == 1)return 1;if(n == 2)return 2;int dp_i, dp_i_2 = 1, dp_i_1 = 2;for(int i = 2; i < n; ++i){dp_i = dp_i_1 + dp_i_2;dp_i_2 = dp_i_1;dp_i_1 = dp_i;}return dp_i;} }; 創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎(jiǎng)勵(lì)來咯，堅(jiān)持創(chuàng)作打卡瓜分現(xiàn)金大獎(jiǎng)

總結(jié)

以上是生活随笔為你收集整理的LeetCode 70. 爬楼梯（动态规划）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。