**不要迷信 DP！**很多时候，动态规划其实是一种带缓存优化的暴力计算。所以未必能得到最优解。

• 入门 + 单序列型 DP
• 双序列型 DP
• 矩阵坐标型 DP
• 背包型 DP
• 区间及其它类型 DP

## 入门 + 单序列型 DP

### LC 746 使用最小花费爬楼梯

【例子】746. 使用最小花费爬楼梯

输入：cost = [10, 15, 20]



输入：cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]



class Solution {
public:
int calc(vector<int> &cache, vector<int> &cost, int cur = -1) {
// 读缓存
if (cache[cur] != 0) {
return cache[cur];
}
int end = cost.size() - 1;
int curcost = cost[cur], nextcost = 0;
if (cur <= end - 2) {
int next1c = calc(cache, cost, cur + 1);
int next2c = calc(cache, cost, cur + 2);
nextcost = min(next1c, next2c);
}
// 总开销 = 当前步骤开销 + 下一步开销
auto total = curcost + nextcost;
// 写缓存
cache[cur] = total;
}
// 规定：到达之后才计算开销
int minCostClimbingStairs(vector<int> &cost) {
// 缓存
vector<int> cache(cost.size());
int cur = -1;
int next1c = INT_MAX, next2c = INT_MAX;
next1c = calc(cache, cost, cur + 1);
next2c = calc(cache, cost, cur + 2);
return min(next1c, next2c);
}
};


class Solution {
public:
int rec(std::vector<int> &cost, int i) {
if (i == 0 || i == 1)
return cost[i];
return min(rec(cost, i - 1), rec(cost, i - 2)) + cost[i];
}
int minCostClimbingStairs(vector<int> &cost) {
int n = cost.size();
return min(rec(cost, n - 1), rec(cost, n - 2));
}
};


class Solution {
public:
int rec(std::vector<int> &cost, std::vector<int> &dp, int i) {
if (i == 0 || i == 1)
return cost[i];
if (dp[i] != -1)
return dp[i];
dp[i] = min(rec(cost, dp, i - 1), rec(cost, dp, i - 2)) + cost[i];
return dp[i];
}
int minCostClimbingStairs(vector<int> &cost) {
int n = cost.size();
std::vector<int> dp(n);
fill(dp.begin(), dp.end(), -1);
return min(rec(cost, dp, n - 1), rec(cost, dp, n - 2));
}
};


class Solution {
public:
int minCostClimbingStairs(vector<int> &cost) {
int n = cost.size();
std::vector<int> dp(n) = {cost[0]， cost[1]};
for (int i = 2; i < n; i++) {
dp[i] = min(dp[i - 1], dp[i - 2]) + cost[i];
}
return min(dp[n - 2], dp[n - 1]);
}
};


class Solution {
public:
int minCostClimbingStairs(vector<int> &cost) {
int n = cost.size();
vector<int> dp(n);
int pprev = cost[0];
int prev = cost[1];
for (int i = 2; i < n; i++) {
auto cur = min(prev, pprev) + cost[i];
pprev = prev;
prev = cur;
}
return min(prev, pprev);
}
};


class Solution {
public:
int minCostClimbingStairs(vector<int> &cost) {
int n = cost.size();
std::vector<int> dp = {cost[0]， cost[1]};
int d = 2; // 依赖的状态数
for (int i = 2; i < n; i++) {
// 比如 i = 2, d = 2，则相当于 dp [0] = min (dp [1], dp [0])
dp[i % d] = min(dp[(i - 1) % d], dp[(i - 2) % d]) + cost[i];
}
return min(dp[0], dp[1]);
}
};


### LC 198 打家劫舍

输入：[1,2,3,1]

偷窃到的最高金额 = 1 + 3 = 4 。


输入：[2,7,9,3,1]

偷窃到的最高金额 = 2 + 9 + 1 = 12 。


class Solution {
public:
int rob(vector<int> &v) {
if (v.size() == 1) {
return v[0];
}
std::vector<int> dp(v.size());
dp[0] = v[0];
dp[1] = v[1];
int dp_max = 0; // 从 0 到 i-2 的最大值
for (size_t i = 2; i < v.size(); i++) {
dp_max = INT_MIN;
for (int j = 0; j <= i - 2; j++) {
dp_max = max(dp_max, dp[j]);
}
dp[i] = dp_max + v[i];
}
print_vec(dp);
return max(dp[v.size() - 1], dp[v.size() - 2]);
}
};


class Solution {
public:
int rob(vector<int> &v) {
if (v.size() == 1) {
return v[0];
}
std::vector<int> dp(v.size());
dp[0] = v[0];
dp[1] = v[1];
int dp_max = 0; // 从 0 到 i-2 的最大值
for (size_t i = 2; i < v.size(); i++) {
dp_max = max(dp_max, dp[i - 2]);
dp[i] = dp_max + v[i];
}
return max(dp[v.size() - 1], dp[v.size() - 2]);
}
};


class Solution {
public:
int rob(vector<int> &v) {
if (v.size() == 1) {
return v[0];
}
int d = 2; //d >= 2 都行
std::vector<int> dp(d);
dp[0] = v[0];
dp[1] = v[1];
int dp_max = 0; // 从 0 到 i-2 的最大值
for (size_t i = 2; i < v.size(); i++) {
dp_max = max(dp_max, dp[(i - 2) % d]);
dp[i % d] = dp_max + v[i];
}
return max(dp[(v.size() - 1) % d], dp[(v.size() - 2) % d]);
}
};


int rob(vector<int> v){
int n = v.size();
if(n == 1) return v[0];
vector<int> dp = {v[0], max(v[0], v[1])};
for (int i = 2; i < n; i++){
dp[i % 2] = max(dp[(i - 1) % 2], dp[(i - 2) % 2] + v[i]);
}
return dp[(n - 1) % 2];
}


### LC 213 打家劫舍 II （环形数组）

Case 1：相当于抹掉最后一间房子。然后用上题解法。

Case 2：相当于抹掉第一间房子。然后用上题解法。