動(dòng)態(tài)規(guī)劃篇：
一、509. 斐波那契數(shù)
思路：動(dòng)態(tài)規(guī)劃五部曲。根據(jù)本題的要求具體劃分：
- 確定dp數(shù)組以及下標(biāo)的含義：dp[i]的定義為：第i個(gè)數(shù)的斐波那契數(shù)值是dp[i]
- 確定遞推公式：狀態(tài)轉(zhuǎn)移方程 dp[i] = dp[i - 1] + dp[i - 2];
- dp數(shù)組如何初始化：dp[0] = 0, dp[1] = 1;
- 確定遍歷順序： 從遞歸公式dp[i] = dp[i - 1] + dp[i - 2];中可以看出，dp[i]是依賴 dp[i - 1] 和 dp[i - 2]，那么遍歷的順序一定是從前到后遍歷的
- 舉例推導(dǎo)dp數(shù)組：
代碼：文章來源地址http://www.zghlxwxcb.cn/news/detail-405741.html
class Solution {
public int fib(int n) {
if (n <= 1) return n;
// 這里設(shè)置為n+1，因?yàn)?到n有n+1個(gè)數(shù)
int[] fib = new int[n + 1];
// 初始化
fib[0] = 0;
fib[1] = 1;
for (int i = 2; i <= n; i++) {
fib[i] = fib[i - 1] + fib[i - 2];
}
return fib[n];
}
}二、70. 爬樓梯
注意：這個(gè)題的初始化存在爭議，這里是默認(rèn)dp[1]=1作為開頭，不考慮dp[0]的情況。
public int climbStairs(int n) {
// 1.確定dp數(shù)組
int[] dp = new int[n + 1];
if (n <= 2) return n;
// 2.初始化dp數(shù)組, 這里不針對dp[0]做單獨(dú)歸一化
dp[1] = 1;
dp[2] = 2;
for (int i = 3; i <= n; i++) {
// 3.4. 確定遞推公式 和 確定遍歷順序
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}三、746. 使用最小花費(fèi)爬樓梯
注意：dp初始化 是dp[0] = 0，dp[1] = 0;
遞推公式是dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
還有注意for循環(huán)中的i <=n。文章來源：http://www.zghlxwxcb.cn/news/detail-405741.html
代碼：
class Solution {
public int minCostClimbingStairs(int[] cost) {
int n = cost.length;
// dp[0] dp[1] 不算是樓梯里 所以索引是n + 1
// 也可以理解成0到n，一共有n+1個(gè)數(shù)
int[] dp = new int[n + 1];
// 初始化
dp[0] = 0;
dp[1] = 0;
// i <= n的意義在于最后要到樓頂，不是只在樓層上
for (int i = 2; i <= n; i++) {
dp[i] = Math.min(cost[i - 1] + dp[i - 1], cost[i - 2] + dp[i - 2]);
}
return dp[n];
}
}到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)刷題（二十八）：509斐波那契數(shù)、70爬樓梯、746 使用最小花費(fèi)爬樓梯的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
