前置知識
解題思路
動態(tài)規(guī)劃（DP，Dynamic Programming）。
其解題思路對比貪心算法的“直接選局部最優(yōu)然后推導(dǎo)出全局最優(yōu)”；傾向于“由之前的結(jié)果推導(dǎo)得到后續(xù)的結(jié)果”。
很多時候二者具有相似性，不必死扣概念。
解題步驟
動態(tài)規(guī)劃題目的核心是dp數(shù)組的概念和構(gòu)建(遞推公式);
所以具體的解題步驟可以分為以下幾步:
- 確定dp數(shù)組（dp table）以及下標(biāo)的含義
- 確定遞推公式
- dp數(shù)組如何初始化
- 確定遍歷順序
- 舉例推導(dǎo)dp數(shù)組
動態(tài)規(guī)劃的debug
每走一步都將dp數(shù)組打印出來, 檢查是否和自己推導(dǎo)和計劃的一致.
當(dāng)出現(xiàn)bug的時候, 思考:
- 這道題目我舉例推導(dǎo)狀態(tài)轉(zhuǎn)移公式了么？
- 我打印dp數(shù)組的日志了么？
- 打印出來了dp數(shù)組和我想的一樣么？
參考文章：動態(tài)規(guī)劃理論基礎(chǔ)
509. 斐波那契數(shù)
題目描述
LeetCode鏈接：https://leetcode.cn/problems/fibonacci-number/description/
解題思路
因為是簡單題, 所以直接給出了遞推公式, 我們只需要先構(gòu)建dp數(shù)組的前兩項, 然后依次向后傳遞推導(dǎo)即可.
代碼
使用dp數(shù)組
class Solution {
public:
int fib(int n) {
vector<int> fei;
fei.push_back(0);
fei.push_back(1);
for(int i=2; i<=n; ++i){
fei.push_back(fei[i-1] + fei[i-2]);
}
return fei[n];
}
};
優(yōu)化空間復(fù)雜度: 不用數(shù)組, 只用兩個變量記錄即可
class Solution {
public:
int fib(int n) {
if(n==0) return 0;
else if(n==1) return 1;
int first=0, second=1;
for(int i=2; i<=n; ++i){
int tmp = first + second;
first = second;
second = tmp;
}
return second;
}
};
70. 爬樓梯
題目描述
LeetCode鏈接：https://leetcode.cn/problems/climbing-stairs/description/
解題思路
本質(zhì)上和前一題的斐波那契數(shù)列是一樣的.
發(fā)現(xiàn)第i階的可能性, 是i-1階和i-2階的和
可以理解為: 從i-1階和i-2階都可以直接到達i階, 所以dp[i]=dp[i-1]+dp[i-2]
代碼
使用dp數(shù)組
class Solution {
public:
int climbStairs(int n) {
vector<int> dp;
dp.push_back(1);
dp.push_back(1);
for(int i=2; i<=n; i++){
dp.push_back(dp[i-1] + dp[i-2]);
}
return dp[n];
}
};
優(yōu)化空間復(fù)雜度: 不用數(shù)組, 只用兩個變量記錄即可
class Solution {
public:
int climbStairs(int n) {
if(n==0 || n==1) return 1;
int first=1, second=1;
for(int i=2; i<=n; i++){
int tmp = first+second;
first = second;
second = tmp;
}
return second;
}
};
746. 使用最小花費爬樓梯
題目描述
LeetCode鏈接：https://leetcode.cn/problems/min-cost-climbing-stairs/description/
解題思路
思路: 動態(tài)規(guī)劃dp[i] 表示從i處起跳的話, 需要支付的費用
那么就有: dp[i] = min(dp[i-1], dp[i-2]) + cost[i];
代碼
使用dp數(shù)組
class Solution {
public:
int minCostClimbingStairs(vector<int>& cost) {
int n=cost.size();
vector<int> dp(n);
dp[0] = cost[0];
dp[1] = cost[1];
for(int i=2; i<n; ++i){
dp[i] = min(dp[i-1], dp[i-2]) + cost[i];
}
return min(dp[n-1], dp[n-2]);
}
};
優(yōu)化空間復(fù)雜度
class Solution {
public:
int minCostClimbingStairs(vector<int>& cost) {
int n=cost.size();
int first = cost[0];
int second = cost[1];
for(int i=2; i<n; ++i){
int tmp = min(first, second) + cost[i];
first = second;
second = tmp;
}
return min(first, second);
}
};
另一種動態(tài)規(guī)劃思路
用另一種思路來構(gòu)建dp數(shù)組:
剛才認為"dp[i]是從i處起跳需要支付的代價", 現(xiàn)在認為"dp[i]是到達i需要支付的代價"
遞推公式也就變?yōu)? dp[i] = min(dp[i-1]+cost[i-1], dp[i-2]+cost[i-2]);
所以最開始的dp[0]和dp[1]初始化為0, dp的長度也設(shè)置為cost.size()+1, 一路推導(dǎo)到dp[cost.size()], 直接return即可文章來源：http://www.zghlxwxcb.cn/news/detail-700449.html
class Solution {
public:
int minCostClimbingStairs(vector<int>& cost) {
vector<int> dp(cost.size() + 1);
dp[0] = 0; // 默認第一步都是不花費體力的
dp[1] = 0;
for (int i = 2; i <= cost.size(); i++) {
dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
}
return dp[cost.size()];
}
};
總結(jié)
本文參考：
斐波那契數(shù)
爬樓梯
使用最小花費爬樓梯文章來源地址http://www.zghlxwxcb.cn/news/detail-700449.html
到了這里，關(guān)于LeetCode刷題筆記【29】：動態(tài)規(guī)劃專題-1（斐波那契數(shù)、爬樓梯、使用最小花費爬樓梯）的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
