跟着灵茶山艾府大佬学习算法思路的day16（并没有在一个月内掌握hot100）
b站链接如下：
DP的参数就是限制，限制就是维度。
买卖股票的最佳时机 II 题目描述：
给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。
在每一天，你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。然而，你可以在 同一天 多次买卖该股票，但要确保你持有的股票不超过一股。
返回 你能获得的 最大 利润 。
示例 1：
1
2
3
4
5
输入：prices = [7,1,5,3,6,4]
输出：7
解释：在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4。
随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6 - 3 = 3。
最大总利润为 4 + 3 = 7 。
示例 2：
1
2
3
4
输入：prices = [1,2,3,4,5]
输出：4
解释：在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4。
最大总利润为 4 。
示例 3：
1
2
3
输入：prices = [7,6,4,3,1]
输出：0
解释：在这种情况下, 交易无法获得正利润，所以不参与交易可以获得最大利润，最大利润为 0。
提示：
1 <= prices.length <= 3 * 1040 <= prices[i] <= 104
思路：
买卖股票这类问题可以分成两种类型，一种是不限制交易次数的，一种是限制交易次数的。
状态机看着玄乎，其实状态说的就是hold这个维度，手上有没有股票这个状态。对于交易k次问题，状态次数就变成了k 次交易 × hold 2种状态 = 2k 个状态节点。
状态机dp本质就是根据状态不同，可以有不同的状态转移方式，之前博客的dp都是一条状态转移方程就解决了。
买卖股票的最佳时机可以只用贪心解决，这一题也可以。买卖股票的最佳时机限制只能交易一次，因此当然要求最大差值；但本题可以交易无限次，所以可以将股价图中所有上升沿都转化为自己的收益，也就是只要明天会比今天涨，那就可以今天买明天卖，这样也可以用贪心解决。
但本题选择用DP来写是为了学会状态机，这个状态机框架可以扩展到所有股票问题：
| 问题 | 约束 | 用什么 |
|---|---|---|
| I | 最多1次 | 贪心就行 |
| II | 无限次 | 贪心 or DP状态机 |
| III | 最多2次 | 必须DP，加交易次数维度 |
| IV | 最多k次 | 必须DP，加交易次数维度 |
| 含冷冻期 | 无限次+冷却 | 必须DP，加冷却状态 |
| 含手续费 | 无限次+费 | 必须DP，手续费影响决策 |
第五天一共有三种可能，什么也不做，收益是0；手上有股票，选择卖出，收益是4；手上没有股票，选择购入，收益是-4。
子问题可以抽象如下，第i天我们可以做的操作也如下图：
经过这样分析，就可以定义状态和状态转移方程了。由于第i-1天的结束也是第i天的开始，dfs(i-1, *)也表示第i天开始的最大利润。第一个参数代码在第几天，第二个参数代表今日是否持有股票。如果是限制交易次数的题目，还需要新增加一项限制，就是已完成的交易次数，这样就需要传入三个参数。
递归边界也值得注意。同时在考虑递归入口时，因为dfs(n-1, 1)不可能比dfs(n-1, 0)更大，所以可以直接从dfs(n-1, 0)开始递归。
最终递推方程如下：
在考虑本题时，要注意一天之内只能允许一次买入和一次卖出，买入和卖出在一天内同时执行是无意义的。
此外，和打家劫舍那种经典的选或不选比起来，打家劫舍是今天选或不选，决定子问题；股票2是昨天选不选，决定今天状态。打家劫舍是主动进行选或不选的选择，而股票2是今天的状态从哪来，更像是选哪个。
代码：
递归：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
var maxProfit = function(prices) {
const n = prices.length;
const dfs = (day, hold) => {
if (day < 0) {
return hold ? -Infinity : 0;
}
if (hold) { // 假如今天有库存，说明昨天有库存没卖出，或昨天没库存但今天买入了
return Math.max(dfs(day - 1, 1), dfs(day - 1, 0) - prices[day]);
}
// 假如今天没库存，说明昨天没库存但也没买入，或昨天有库存但在今天卖出了
return Math.max(dfs(day - 1, 0), dfs(day - 1, 1) + prices[day]);
}
// 对最后一天而言，再持仓就卖不出去了
return dfs(n - 1, 0);
};
递归+记忆化（会卡最后一个用例）：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
var maxProfit = function(prices) {
const n = prices.length;
const memo = Array.from({ length : n }, () => new Array(2).fill(-1));
const dfs = (day, hold) => {
if (day < 0) {
return hold ? -Infinity : 0;
}
if (memo[day][hold] !== -1) {
return memo[day][hold];
}
if (hold) {
memo[day][hold] = Math.max(dfs(day - 1, 1), dfs(day - 1, 0) - prices[day]);
return memo[day][hold];
}
memo[day][hold] = Math.max(dfs(day - 1, 0), dfs(day - 1, 1) + prices[day]);
return memo[day][hold];
}
return dfs(n - 1, 0);
};
递推（可以通过全部用例，但效率不佳）：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
var maxProfit = function(prices) {
const n = prices.length;
const dp = Array.from({ length: n + 1 }, () => new Array(2).fill(0));
// 多了初始状态，需要n+1
dp[0][1] = -Infinity; // 还没开始，不可能持有
for (let day = 0; day < n; day++) {
// prices的day不加1的原因是dp[0]是初始状态基本行，day1才是第一天的结果
dp[day + 1][1] = Math.max(dp[day][1], dp[day][0] - prices[day]);
dp[day + 1][0] = Math.max(dp[day][0], dp[day][1] + prices[day]);
}
return dp[n][0];
};
因为dpi+1只用到dpi，所以可以滚动数组：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
var maxProfit = function(prices) {
const n = prices.length;
const dp = Array.from({ length: 2 }, () => new Array(2).fill(0));
// 多了初始状态，需要n+1
dp[0][1] = -Infinity; // 还没开始，不可能持有
for (let day = 0; day < n; day++) {
// prices的day不加1的原因是dp[0]是初始状态基本行，day1才是第一天的结果
dp[(day + 1) % 2][1] = Math.max(dp[day % 2][1], dp[day % 2][0] - prices[day]);
dp[(day + 1) % 2][0] = Math.max(dp[day % 2][0], dp[day % 2][1] + prices[day]);
}
return dp[n % 2][0];
};
甚至可以两个变量（因为状态实在少，用两个变量的一维数组同理）：
1
2
3
4
5
6
7
8
9
10
11
12
13
var maxProfit = function(prices) {
let hold = -Infinity, cash = 0;
for (let day = 0; day < prices.length; day++) {
let newHold = Math.max(hold, cash - prices[day]); // 如果今天持有
let newCash = Math.max(cash, hold + prices[day]); // 如果今天空仓
hold = newHold;
cash = newCash;
}
return cash;
};
总结：
特点的地方在于有两条状态转移方程，这是由于状态这一dp维度决定的。虽然类似背包问题也多具有容量这一个维度，但不管容量如何，所能进行的行为总是一致的，只需要一条转移方程。但对于状态机问题来说，状态不同所能进行的行为是不相同的。只有当维度改变了能做什么时，才需要状态机。
买卖股票的最佳时机含冷冻期 题目描述：
给定一个整数数组prices，其中第 prices[i] 表示第 *i* 天的股票价格 。
设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:
- 卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
示例 1:
1
2
3
输入: prices = [1,2,3,0,2]
输出: 3
解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]
示例 2:
1
2
输入: prices = [1]
输出: 0
提示：
1 <= prices.length <= 50000 <= prices[i] <= 1000
思路：
冷冻期就是不能连着买入卖出，有点类似于打家劫舍，也可以从右到左思考。因为在卖出后，无法在第二天买入，所以在上题代码基础上，在卖出处多往前一天即可。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
var maxProfit = function(prices) {
const n = prices.length;
const memo = Array.from({ length : n }, () => new Array(2).fill(-1));
const dfs = (day, hold) => {
if (day < 0) {
return hold ? -Infinity : 0;
}
if (memo[day][hold] !== -1) {
return memo[day][hold];
}
if (hold) { // 假如今天有库存，如果是在今天买入，要保持两天空仓
memo[day][hold] = Math.max(dfs(day - 1, 1), dfs(day - 2, 0) - prices[day]);
return memo[day][hold];
}
memo[day][hold] = Math.max(dfs(day - 1, 0), dfs(day - 1, 1) + prices[day]);
return memo[day][hold];
}
return dfs(n - 1, 0);
};
总结：
基于上一题改改就行。上一题是母题，判题比较严格，这题判题比较松。
买卖股票的最佳时机 IV 题目描述：
给你一个整数数组 prices 和一个整数 k ，其中 prices[i] 是某支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。也就是说，你最多可以买 k 次，卖 k 次。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
示例 1：
1
2
3
输入：k = 2, prices = [2,4,1]
输出：2
解释：在第 1 天 (股票价格 = 2) 的时候买入，在第 2 天 (股票价格 = 4) 的时候卖出，这笔交易所能获得利润 = 4-2 = 2 。
示例 2：
1
2
3
4
输入：k = 2, prices = [3,2,6,5,0,3]
输出：7
解释：在第 2 天 (股票价格 = 2) 的时候买入，在第 3 天 (股票价格 = 6) 的时候卖出, 这笔交易所能获得利润 = 6-2 = 4 。
随后，在第 5 天 (股票价格 = 0) 的时候买入，在第 6 天 (股票价格 = 3) 的时候卖出, 这笔交易所能获得利润 = 3-0 = 3 。
提示：
1 <= k <= 1001 <= prices.length <= 10000 <= prices[i] <= 1000
思路：
因为增加了一个只能交易k次的限制，所以需要增加一个新的维度，一般约定为参数j，表示至多完成j笔交易。买入卖出是两两成对的，有买入一定有卖出，买入加上卖出才算是一次交易。在每次买入或者卖出时，需要利用这个限制，增加一个维度，把交易次数减一。
这题需要注意的是递归边界，多了一个j不可能小于零的初始化。
