Problem: 70. 爬樓梯
題目描述
思路
由于本題目中第i層臺(tái)階只能由于第i- 1層臺(tái)階和第i-2層臺(tái)階走來(lái)，所以可以聯(lián)想到動(dòng)態(tài)規(guī)劃，具體如下：
1.定義多階段決策模型：對(duì)于每一上臺(tái)階看作一種狀態(tài)；
2.定義狀態(tài)轉(zhuǎn)移方程：int[] dp = new int[n + 1]用于記錄第i個(gè)臺(tái)階可以走到的走法；dp[i] = dp[i - 1] + dp[i - 2];
解題方法
1.定義數(shù)組int[] dp = new int[n + 1]用于記錄第i個(gè)臺(tái)階可以走到的走法
2.初始化dp[1] = 1； dp[2] = 2;
3.從dp數(shù)組下標(biāo)為3處開(kāi)始完成動(dòng)態(tài)轉(zhuǎn)移方程；
4.返回dp[n]
復(fù)雜度
時(shí)間復(fù)雜度:
O ( n ) O(n) O(n);其中 n n n為臺(tái)階數(shù)
空間復(fù)雜度:文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-809669.html
O ( n ) O(n) O(n)文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-809669.html
Code
class Solution {
/**
* Dynamic programing
* @param n The number of stage
* @return int
*/
public int climbStairs(int n) {
if (n <= 2) {
return n;
}
//Record how many moves there are on step i
int[] dp = new int[n + 1];
dp[1] = 1;
dp[2] = 2;
for (int i = 3; i <= n; ++i) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
}
class Solution {
public:
int climbStairs(int n) {
if (n <= 2) {
return n;
}
vector<int> dp(n + 1);
dp[1] = 1;
dp[2] = 2;
for (int i = 3; i <= n; ++i) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
};
到了這里，關(guān)于力扣70. 爬樓梯（動(dòng)態(tài)規(guī)劃 Java，C++解法）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
