算法思路
Source
Edit
History

undefined

动态规划

dynamic programming

动态规划和递归或者分治 没有根本上的区别（关键看有无最优的子结构）
共性：找到重复子问题
差异性：最优子结构、中途可以淘汰次优解

  1. 斐波那契数列 （一维数组）
  2. 路径计数 （二维数组）

状态转移方程（DP方程）
opt[i, j] = opt[i+1, j] + opt[i, j+1]

完整逻辑：
if a[i, j] = ‘空地’:
opt[i, j] = opt[i+1, j] + opt[i, j+1]
else:
opt[i, j] = 0

动态规划关键点

  1. 最优子结构 opt[n] = best_of(opt[n-1], opt[n-2], …)
  2. 存储中间状态：opt[i]
  3. 递推公式（美其名曰：状态转移方程或者DP方程）
    Fib：opt[i] = opt[n-1] + opt[n-2]
    二维路径：opt[i, j] = opt[i+1][j] + opt[i][j+1] （且判断 a[i][j] 是否空地）

问题：最长公共子序列
思路：

  1. 因为需要求最长子序列，因此我们可以从最后一个字符看起，然后依次向前找
  2. 转换为子问题，当找到最后一个相同的字符时，即转换为需要求此字符前面两个字符串的最长公共子序列
  3. 经验，转换为二维数组，行和列分别为两个字符串。定义 dp 二维数组时可以为字符串长度+1
    如：字符串 abcde 、ace
    | | a | b | c | d | e |
    | a | 1 | 1 | 1 | 1 | 1 |
    | c | 1 | 1 | 2 | 2 | 2 |
    | e | 1 | 1 | 2 | 2 | 3 |
    得出结论：
    if S1[n-1] != S2[m-1] : LCS[s1, s2] = Max(LCS[s1-1, s2], LCS[s1, s2-1])
    if S1[n-1] == S2[m-1] : LCS[s1, s2] = LCS[s1-1, s2-1] + 1

小结：

  1. 打破自己的思维惯性，形成机器思维
  2. 理解复杂逻辑的关键
  3. 也是职业进阶的要点要领

实战题目：
爬楼梯

  1. 可以爬1，2，3级台阶: F(n) = F(n-1)+F(n-2)+F(n-3)
  2. 相邻两步的步伐不能相同。

房屋偷盗问题：leetcode 198

  1. 子问题
  2. 状态定义
  3. dp方程

股票问题

leetcode 121 买卖股票的最佳时机
一个方法团灭6道股票问题
https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iv/solution/yi-ge-tong-yong-fang-fa-tuan-mie-6-dao-gu-piao-w-5/

关键点：天数、允许买的次数k、是否持有股票
第一题是只进行一次交易，相当于 k = 1；第二题是不限交易次数，相当于 k = +infinity（正无穷）；
第三题是只进行 2 次交易，相当于 k = 2；
剩下两道也是不限次数，但是加了交易「冷冻期」和「手续费」的额外条件，其实就是第二题的变种，都很容易处理。

状态转移方程：
dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + price[i])
第 i 天，没有持有股票，当前还剩 k 次买股票的机会。
要么就是 i-1 天，没有持有股票，第 i-1 天有 k 次买股票的机会
要么就是 i-1 天，持有股票，在第 i 天卖掉了股票，第 i-1 天有 k 次买股票的机会

dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - price[i])
第 i 天，持有股票，当前还剩 k 次买股票的机会
要么就是 i-1 天，持有股票，第 i-1 天有 k 次买股票的机会
要么就是 i-1 天，没有持有股票，第 i-1 天有 k-1 次买股票的机会，然后第 i 天买了股票

初始状态条件：
dp[-1][k][0] = 0
没有持股票，此时为 0
dp[-1][k][1] = -inf
在 -1 天不可能持有股票，因此为 -inf

注意：初始条件要设置恰当，否则可能导致数值溢出；还有要注意可能不买卖股票的0收益比买卖股票还高。

股票问题代码

// 状态规划方程
// i 天数 k 买股票的机会 0/1 是否持有股票
// dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + price[i])
// dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - price[i])
// 初始状态
// dp[i-1][k][0] = 0
// dp[i-1][k][1] = -inf

// 由于此题目中只能买卖一次，因此 k = 1
// 状态方程进行简化
// dp[i][1][0] = max(dp[i-1][1][0], dp[i-1][1][1] + prices[i])
// dp[i][1][1] = max(dp[i-1][1][1], dp[i-1][0][0] - prices[i])
// = max(dp[i-1][1][1], -prices[i])
// 解释：k = 0 的 base case，所以 dp[i-1][0][0] = 0。
// 因此状态方程如下:
// dp[i][0] = max(dp[i-1][0], dp[i-1][1] + price[i])
// dp[i][1] = max(dp[i-1][1], -price[i])

#include
#include
#include <string.h>
#include <limits.h>
using namespace std;

// class Solution {
// public:
// int maxProfit(vector& prices) {
// if (prices.empty()) return 0;
// vector<vector> dp(prices.size()+1, vector(2, 0));
// dp[0][0] = 0;
// dp[0][1] = INT_MIN;

// for (int i = 1; i < dp.size(); i++) {
// dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i-1]);
// dp[i][1] = max(dp[i-1][1], -prices[i-1]);
// }
// return dp[dp.size()-1][0];
// }
// };

// class Solution {
// public:
// int maxProfit(vector& prices) {
// if (prices.empty()) return 0;
// int dp_0 = 0;
// int dp_1 = INT_MIN;

// for (int i = 0; i < prices.size(); i++) {
// dp_0 = max(dp_0, dp_1+prices[i]);
// dp_1 = max(dp_1, -prices[i]);
// }
// return dp_0;
// }
// };

// 股票问题2 可以尽可能多的买卖股票
// k 的值就是尽可能大，因此直接去掉 k 这个参数即可
// 状态方程可以定义为：
// dp[i][0] = max(dp[i-1][0], dp[i-1][1] + price[i])
// dp[i][1] = max(dp[i-1][1], dp[i-1][0] - price[i])
// 初始状态
// dp[-1][0] = 0;
// dp[-1][1] = INT_MIN;

// class Solution {
// public:
// int maxProfit(vector& prices) {
// if (prices.empty()) return 0;
// vector<vector> dp(prices.size()+1, vector(2, 0));
// dp[0][0] = 0;
// dp[0][1] = INT_MIN;
// for (int i = 1; i < dp.size(); i++) {
// dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i-1]);
// dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i-1]);
// }
// return dp[dp.size()-1][0];
// }
// };

// class Solution {
// public:
// int maxProfit(vector& prices) {
// if (prices.empty()) return 0;
// int dp_0 = 0;
// int dp_1 = INT_MIN;
// for (int i = 0; i < prices.size(); i++) {
// dp_0 = max(dp_0, dp_1 + prices[i]);
// dp_1 = max(dp_1, dp_0 - prices[i]);
// }
// return dp_0;
// }
// };

// 股票问题3 最多可以完成 两笔 交易
// k 最大可以为2
// dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + price[i])
// dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - price[i])
// 因此需要两层循环，一层是天数，一层是买股票次数 k
// 初始条件,第一天要么买，要么不买
// dp[0][0][0] = 0;
// dp[0][1][1] = -prices[0];
// dp[0][0][1] = dp[0][1][0] = dp[0][2][0] = dp[0][2][1] = SHRT_MIN;

// 这道题一定要注意对于不存在的值，可能出现数值溢出，所以使用了 SHRT_MIN
// 还有有可能不买卖股票的收益最高

// class Solution {
// public:
// int maxProfit(vector& prices) {
// if (prices.empty()) return 0;

// int N = prices.size();
// int BUY_COUNT = 2;
// vector<vector<vector>> dp(N, vector<vector>(BUY_COUNT+1, vector(2, 0)));

// // 初始条件,第一天要么买，要么不买
// dp[0][0][0] = 0;
// dp[0][1][1] = -prices[0];
// dp[0][0][1] = dp[0][1][0] = dp[0][2][0] = dp[0][2][1] = SHRT_MIN;

// for (int i = 1; i < N; i++) {
// for (int j = BUY_COUNT; j > 0; j–) {
// dp[i][j][0] = max(dp[i-1][j][0], dp[i-1][j][1]+prices[i]);
// dp[i][j][1] = max(dp[i-1][j][1], dp[i-1][j-1][0]-prices[i]);
// }
// }
// return max(dp[N-1][0][0], max(dp[N-1][1][0], dp[N-1][2][0]));
// }
// };

// 优化过程
// dp[i][1][0] = max(dp[i-1][1][0], dp[i-1][1][1]+prices[i])
// dp[i][1][1] = max(dp[i-1][1][1], dp[i-1][0][0]-prices[i]) 其中 dp[i][0][0] = 0 也可写成 -prices[i]
// dp[i][2][0] = max(dp[i-1][2][0], dp[i-1][2][1]+prices[i])
// dp[i][2][1] = max(dp[i-1][2][1], dp[i-1][1][0]-prices[i])

// class Solution {
// public:
// int maxProfit(vector& prices) {
// if (prices.empty()) return 0;
// int N = prices.size();

// int dp_i_1_0 = SHRT_MIN;
// int dp_i_1_1 = -prices[0];
// int dp_i_2_0 = SHRT_MIN;
// int dp_i_2_1 = SHRT_MIN;
// for (int i = 1; i < N; i++) {
// dp_i_1_0 = max(dp_i_1_0, dp_i_1_1+prices[i]);
// dp_i_1_1 = max(dp_i_1_1, -prices[i]);
// dp_i_2_0 = max(dp_i_2_0, dp_i_2_1+prices[i]);
// dp_i_2_1 = max(dp_i_2_1, dp_i_1_0-prices[i]);
// }
// return max(0, max(dp_i_1_0, dp_i_2_0, 0));
// }
// };

// 股票问题4 股票可以买卖K次
// dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1]+prices[i])
// dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0]-prices[i])
// 初始条件
// 第一天:
// dp[0][k][0] = 0
// dp[0][k][1] = -prices[0]
// 还有一个优化点，因为总共有N天，所以 k 一定小于等于 N/2 次。大于 N/2 的 k 的值其实没有必要保存，认为 k 为正无穷即可
// 当 k 为无穷大的时候，状态方程可写为：
// dp[i][0] = max(dp[i-1][0], dp[i-1][1]+prices[i])
// dp[i][1] = max(dp[i-1][1], dp[i-1][0]-prices[i])
// 初始状态：第一天
// dp[0][0] = 0
// dp[0][1] = -prices[i]

// class Solution {
// public:
// int maxProfit(int k, vector& prices) {
// if (prices.empty()) return 0;
// int N = prices.size();
// if (k > N/2) {
// // 直接认为 k 无穷大
// vector<vector> dp(N, vector(2, 0));
// dp[0][0] = 0;
// dp[0][1] = -prices[0];
// for (int i = 1; i < N; i++) {
// dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i]);
// dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i]);
// }
// return dp[N-1][0];
// }
// // 此时考虑 k 的情况
// vector<vector<vector>> dp(N, vector<vector>(k+1, vector(2, 0)));
// for (int m = 0; m < N; m++) {
// for (int n = k; n >= 1; n–) {
// if (m - 1 == -1) {
// // 处理第一天
// dp[0][n][0] = 0;
// dp[0][n][1] = -prices[m];
// continue;
// }
// dp[m][n][0] = max(dp[m-1][n][0], dp[m-1][n][1] + prices[m]);
// dp[m][n][1] = max(dp[m-1][n][1], dp[m-1][n-1][0] - prices[m]);
// }
// }
// int res = 0;
// for (int j = k; j >= 1; j–) {
// res = max(res, dp[N-1][j][0]);
// }
// return res;
// }
// };

// 股票问题5 买卖股票包含冷冻期，第n天卖出股票后，第n+1天不能买，需要冷冻一天，第n+2天才能买。买卖次数不限制
// 状态方程：
// dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])
// dp[i][1] = max(dp[i-1][1], dp[i-2][0] - prices[i])
// 初始条件，第一天和第二天：
// dp[0][0] = 0
// dp[0][1] = -prices[0]
// dp[1][0] = max(0, -prices[0]+prices[1]) 第二天没有持有股票，则说明要么第1天买了，第2天卖了。要么第1天、第2天都没有买
// dp[1][1] = max(-prices[0], -prices[1]) 第二天持有股票，则说明要么是第1天买股票了，第2天没有动；要么是第1天没有买，第2天买股票了

// class Solution {
// public:
// int maxProfit(vector& prices) {
// if (prices.empty()) return 0;
// // 至少2天时间，否则无法进行股票买卖
// if (prices.size() < 2) return 0;
// int N = prices.size();
// vector<vector> dp(N, vector(2, 0));
// dp[0][0] = 0;
// dp[0][1] = -prices[0];
// dp[1][0] = max(0, -prices[0] + prices[1]);
// dp[1][1] = max(-prices[0], -prices[1]);
// for (int i = 2; i < N; i++) {
// dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i]);
// dp[i][1] = max(dp[i-1][1], dp[i-2][0] - prices[i]);
// }
// return dp[N-1][0];
// }
// };

// 股票问题6 买卖需要手续费，指买入和卖出需要收取手续费，但买入和卖出这一个整个过程只收一次手续费
// 因此我们可以在买股票设置收取手续费；或者在卖出股票的时候收取手续费
// 买卖次数不限制
// dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])
// dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i] - fee)
// 初始条件
// dp[0][0] = 0
// dp[0][1] = -prices[0] - fee

class Solution {
public:
int maxProfit(vector& prices, int fee) {
if (prices.empty() || prices.size() < 2) return 0;
int N = prices.size();
vector<vector> dp(N, vector(2, 0));
dp[0][0] = 0;
dp[0][1] = -prices[0] - fee;
for (int i = 1; i < N; i++) {
dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i]);
dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i] - fee);
}
return dp[N-1][0];
}
};

int main() {
Solution* s = new Solution();
vector prices = {1, 3, 2, 8, 4, 9};
int fee = 2;
int res = s->maxProfit(prices, fee);
std::cout << res << std::endl;
return 0;
}