理論基礎(chǔ)

動(dòng)態(tài)規(guī)劃，簡(jiǎn)稱 DP，其中的每一個(gè)狀態(tài)一定是由上一個(gè)狀態(tài)推導(dǎo)出來(lái)的，而貪心算法沒(méi)有狀態(tài)推導(dǎo)，只是從局部直接選最優(yōu)。

動(dòng)態(tài)規(guī)劃的五步：

1. 確定 dp 數(shù)組以及下標(biāo)的含義
2. 確定遞推公式
3. dp 數(shù)組如何初始化
4. 確定遍歷順序
5. 舉例推導(dǎo) dp 數(shù)組

Leetcode 509-斐波那契數(shù)

題目描述

https://leetcode.cn/problems/fibonacci-number/description/

解題思路

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

注意考慮 n=0 的情況，如果不加限制條件直接寫(xiě) dp[1] = 1 會(huì)報(bào)錯(cuò)因?yàn)閿?shù)組越界

Leetcode 70-爬樓梯

題目描述

https://leetcode.cn/problems/climbing-stairs/description/

解題思路

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

Leetcode 746-用最小花費(fèi)爬樓梯

題目描述

https://leetcode.cn/problems/min-cost-climbing-stairs/description/

解題思路

本題的解題思路繼承爬樓梯，在此基礎(chǔ)上還需要考慮爬樓梯的費(fèi)用

class Solution {
public:int minCostClimbingStairs(vector<int>& cost) {vector<int> dp(cost.size());//dp保存的是到當(dāng)前樓梯的最低花費(fèi)int n = cost.size();dp[0] = 0;dp[1] = 0;for (int i =2; i < n;i++){dp[i] = min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]);}int minExpense = min(dp[n-1]+cost[n-1],dp[n-2]+cost[n-2]);return minExpense;}
};