先導(dǎo)知識(shí)：
1、動(dòng)態(tài)規(guī)劃常見題型
動(dòng)態(tài)規(guī)劃基礎(chǔ)問題
背包問題
打家劫舍
股票問題
子序列問題
2、動(dòng)態(tài)規(guī)劃五部曲
（1）確定dp數(shù)組的定義及下標(biāo)的含義
（2）確定遞推公式
（3）dp數(shù)組如何初始化
（4）遍歷順序
（5）打印dp數(shù)組
LeetCode509：509. 斐波那契數(shù)
題目描述：
斐波那契數(shù)?（通常用?F(n)?表示）形成的序列稱為?斐波那契數(shù)列?。該數(shù)列由?0?和?1?開始，后面的每一項(xiàng)數(shù)字都是前面兩項(xiàng)數(shù)字的和。也就是：
F(0) = 0，F(xiàn)(1)?= 1 F(n) = F(n - 1) + F(n - 2)，其中 n > 1
給定?n?，請(qǐng)計(jì)算?F(n)?。
示例 1：
輸入：n = 2 輸出：1 解釋：F(2) = F(1) + F(0) = 1 + 0 = 1
解題思路：
利用動(dòng)規(guī)五部曲來分析：
（1）確定dp數(shù)組以及下標(biāo)含義
dp[i]代表第i個(gè)位置的數(shù)值是dp[i]
(2)遞推公式
dp[i] = dp[i-1]+dp[i-2]
(3)dp數(shù)組初始化
dp[0]=0;
dp[1]=1;
(4)遍歷的順序
從前往后文章來源：http://www.zghlxwxcb.cn/news/detail-833999.html
完整代碼：文章來源地址http://www.zghlxwxcb.cn/news/detail-833999.html
public int fib(int n) {
if(n<=1){
return n;
}
int[] dp = new int[n+1];
dp[0]=0;
dp[1]=1;
for(int i=2;i<=n;i++) {
dp[i] = dp[i-1]+dp[i-2];
}
return dp[n];
}LeetCode70：70. 爬樓梯
題目描述：
假設(shè)你正在爬樓梯。需要?n?階你才能到達(dá)樓頂。
每次你可以爬?1?或?2?個(gè)臺(tái)階。你有多少種不同的方法可以爬到樓頂呢？
示例 1：
輸入：n = 2 輸出：2 解釋：有兩種方法可以爬到樓頂。 1. 1 階 + 1 階 2. 2 階
解題思路：
利用動(dòng)規(guī)五部曲來分析：
（1）確定dp數(shù)組以及下標(biāo)含義
dp[i]:代表爬到第i個(gè)臺(tái)階有dp[i]種不同的方法
(2)遞推公式
最后一步可能是從i-1的位置走一步到達(dá)樓頂，也可能是從i-2的位置一次走兩節(jié)臺(tái)階到達(dá)的樓頂，所以可以推導(dǎo)出以下遞推公式：
? ? ? ? ? dp[i] = dp[i-1]+dp[i-2]
(3)dp數(shù)組初始化
dp[1]=1;
dp[2]=2;
(4)遍歷的順序
從前往后
完整代碼：
public int climbStairs(int n) {
if (n <= 1) {
return n;
}
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];
}
?
?LeetCode746：746. 使用最小花費(fèi)爬樓梯
題目描述：
給你一個(gè)整數(shù)數(shù)組?cost?，其中?cost[i]?是從樓梯第?i?個(gè)臺(tái)階向上爬需要支付的費(fèi)用。一旦你支付此費(fèi)用，即可選擇向上爬一個(gè)或者兩個(gè)臺(tái)階。
你可以選擇從下標(biāo)為?0?或下標(biāo)為?1?的臺(tái)階開始爬樓梯。
請(qǐng)你計(jì)算并返回達(dá)到樓梯頂部的最低花費(fèi)。
示例 1：
輸入：cost = [10,15,20] 輸出：15 解釋：你將從下標(biāo)為 1 的臺(tái)階開始。 - 支付 15 ，向上爬兩個(gè)臺(tái)階，到達(dá)樓梯頂部。 總花費(fèi)為 15 。
解題思路：
利用動(dòng)規(guī)五部曲來分析：
(1)確定dp數(shù)組以及下標(biāo)含義
dp[i]存放的是達(dá)到i臺(tái)階的時(shí)候所需要的最低花費(fèi)
(2)遞推公式
由于最后一步可能是從i-1走一步到達(dá)，也可能是在i-2的位置走一步到達(dá)，所以dp[i]=dp[i-1]+cost[i-1]或者dp[i]=dp[i-2]+cost[i-2],?這兩個(gè)中的最小值就是題目中需要的最低花費(fèi)
公式：dp[i] = Math.min(dp[i-1] + cost[i-1], dp[i-2]+cost[i-2]);
(3)dp數(shù)組初始化
dp[0] = 0;
dp[1] = 0;
(4)遍歷的順序
從前往后
完整代碼：
public int minCostClimbingStairs(int[] cost) {
//初始化dp
int len = cost.length;
int[] dp = new int[len + 1];
dp[0] = 0;
dp[1] = 0;
for(int i = 2; i <= len; i++) {
dp[i] = Math.min(dp[i-1] + cost[i-1], dp[i-2]+cost[i-2]);
}
return dp[len];
}到了這里，關(guān)于算法練習(xí) Day38 | LeetCode509,70,746的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
