知识点
知识点
股票买卖问题
股票买卖问题，是经典的动态规划问题，该问题有很多种变种，使用动态规划可以很容易解决
经典例题：股票买卖问题有很多变种，最经典的问题如下。它的变种有：一、是只进行一次交易，相当于 k = 1；二、是不限交易次数，相当于 k = +infinity（正无穷）；三、只进行 2 次交易，相当于 k = 2；剩下两道、也是不限交易次数，但是加了交易「冷冻期」和「手续费」的额外条件，其实就是第二题的变种，都很容易处理
// 经典股票买卖问题 给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。 注意：你不能同时参与多笔交易（必须在再次购买前，卖出之前的股票） 返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0
经典问题解题思路：
动态规划问题，首先我们需要穷举出所有状态。
状态有三个，第一个是天数，第二个是当天允许交易的最大次数，第三个是当前的持有状态（我们用 1 表示持有，0 表示没有持有）。我们用一个三维数组 dp 就可以装下这几种状态的全部组合，用 for 循环就能完成穷举。
根据穷举的状态，我们可以定义dp数组了。该题中，dp数组为一个三维数组，第一维是天数，第二维是操作数，第三维是持有状态，dp数组定义为：当前状态下的最大利润
穷举出状态后，明确选择。选择有3个，买入、卖出、无操作。
明确了状态和选择后，我们需要思考每种「状态」有哪些「选择」，应该如何更新「状态」。根据题目，我们的3个选择，都是和「持有状态」相关的，所以只看「持有状态」，可以列出状态转移方程：
// 第i天持有状态为0，说明之前有两种情况：昨天本来就没有持有，进入今天然后无操作；昨天持有股票，然后今天将股票卖掉。 dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i]); // 第i天持有状态为1，说明之前有两种情况：昨天持有股票，无操作进入今天；昨天没有持有股票，到了今天买了股票，操作数-1，今天持有状态更新为1 dp[i][k][1] = max(dp[i-1][k-1][0] - prices[i], dp[i-1][k][1]);
最后，base case确定
// 没有开始，没有持有，最大利润为0 dp[-1][k][0] = 0; // 没有开始，持有，该状态不可能。使用负无穷数，表示不可能 dp[-1][k][1] = -infinity; // 第i天时，如果操作数k为0，表示没有操作机会了，因此当前最大利润必定为0 dp[i][0][0] = 0; // 第i天时，如果操作数k为0，表示没有操作机会，没有操作机会的情况下不可能持有股票，因此用负无穷表示不可能 dp[i][0][1] = -infinity;
股票买卖多个问题全解答
k=1的股票买卖问题
解题思路：
当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]);
base case 为：
dp[-1][1][0] = 0; dp[-1][1][1] = -infinity; dp[i][0][0] = 0; dp[i][0][1] = -infinity;
结合状态转移方程和base case可以得出，状态转移方程和base case可以进行简化，简化结果为：
省略k这一个维度 dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i]); dp[i][1] = max(dp[i-1][1], -prices[i]);
dp[-1][0] = 0; dp[-1][1] = -infinity; dp[i][0] = 0; // 因为状态转移方程不和dp[i][0][1]有关，因此该base case可以不考虑了
综上，整个的算法如下：
int n = prices.length; int[][] dp = new int[n][2]; // 不需要base case，因为-1的情况在遍历时已经考虑了 // 遍历状态 for (int i = 0; i < n; i++) { // 专门对i==0时，赋值dp[0][0]和dp[0][1] if (i - 1 == -1) { dp[i][0] = 0; dp[i][1] = -prices[0]; continue; } dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]); dp[i][1] = Math.max(dp[i - 1][1], - prices[i]); } // 返回结果 return dp[n - 1][0];k=+infinity时的股票买卖
解题思路：
如果k为正无穷，我们就可以认为k和k-1都是一样的了。所以可以简化状态转移方程：
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]); = max(dp[i-1][k][1], dp[i-1][k][0] - prices[i]); 因此，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]);base case为：
dp[-1][0] = 0; dp[-1][1] = -infinity; dp[i][0] = 0;
最终，算法为：
int n = prices.length; // dp数组 int[][] dp = new int[n][2]; // 遍历状态 for (int i = 0; i < n; i++) { if (i - 1 == -1) { dp[i][0] = 0; dp[i][1] = -prices[i]; continue; } dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]); dp[i][1] = Math.max(dp[i - 1][1], dp[ i- 1][0] - prices[i]); } // 返回结果 return dp[n - 1][0];k=+infinity并且含有冷冻期
解题思路：
整体思路和上述的k=+infinity相似，只是状态转移方程需要改变一下：
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]);
最终的算法为：
int n = prices.length; // dp数组 int[][] dp = new int[n][2]; // 遍历状态 for (int i = 0; i < n; i++) { if (i - 1 == -1) { dp[i][0] = 0; dp[i][1] = -prices[i]; continue; } if (i - 2 == -1) { // 不光要考虑i-1==-1，还要考虑i-2==-1的情况 dp[i][0] = Math.max(0, -prices[0] + prices[1]); dp[i][1] = Math.max(-prices[0], -prices[1]); continue; } dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]); dp[i][1] = Math.max(dp[i - 1][1], dp[i - 2][0] - prices[i]); } // 返回结果 return dp[n - 1][0];k=2时的股票买卖
解题思路：
k = 2 和前面题目的情况稍微不同，因为上面的情况都和 k 的关系不太大。要么 k 是正无穷，状态转移和 k 没关系了；要么 k = 1，跟 k = 0 这个 base case 挨得近，最后也被消掉了
状态转移方程：
// 没有可以化简的地方 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][0] - prices[i], dp[i-1][k][1]);
这道题由于没有消掉 k 的影响，所以必须要用 for 循环对 k 进行穷举才是正确的。因此，该题目的算法应该为：
int n = prices.length; // 定义dp数组 int[][][] dp = new int[n][3][2]; int maxK = 2; for (int i = 0; i < n; i++) { for (int k = maxK; k >= 1; k--) { if (i - 1 == -1) { dp[i][k][0] = 0; dp[i][k][1] = -prices[0]; continue; } dp[i][k][0] = Math.max(dp[i - 1][k][0], dp[i - 1][k][1] + prices[i]); dp[i][k][1] = Math.max(dp[i - 1][k - 1][0] - prices[i], dp[i - 1][k][1]); } } return dp[n - 1][maxK][0];K=任意整数时的股票买卖
解题思路：
和k=2时的思路一样，这里不再列出。
LeetCode算法题
LeetCode算法题
651.【四键键盘】
解题思路：
对于如何在 N 次敲击按钮后得到最多的 A，我们穷举即可，对于每次按键，我们可以穷举四种可能，很明显就是一个动态规划问题。
思路一：
对于动态规划问题，首先明白状态和选择。选择有4种，即题目中的四种按键；状态可以定义三种，第一个状态是剩余的按键次数，用n表示；第二个状态是当前屏幕上字符 A 的数量，用a_num表示；第三个状态是剪切板中字符 A 的数量，用copy表示
对于如此定义「状态」，就可以知道 base case：当剩余次数n为 0 时，a_num就是我们想要的答案。
最后，确定状态转移方程。结合选择，我们可以列出如下的状态转移：
dp(n - 1, a_num + 1, copy), # A 解释：按下 A 键，屏幕上加一个字符 同时消耗 1 个操作数 dp(n - 1, a_num + copy, copy), # C-V 解释：按下 C-V 粘贴，剪切板中的字符加入屏幕 同时消耗 1 个操作数 dp(n - 2, a_num, a_num) # C-A C-C 解释：全选和复制必然是联合使用的， 剪切板中 A 的数量变为屏幕上 A 的数量 同时消耗 2 个操作数
可以看到问题的规模n在不断减小，肯定可以到达n = 0的 base case，所以这个思路是正确。
使用dp数组消除重叠子问题即可。
但是，该思路并不很好，因为结合状态来看，该算法的时间复杂度非常高，至少为O(N^3)。这说明，该思路状态定义的不好。
思路二：
选择依然只有4个，即题目中的四种按键。
状态我们只定义一个，也就是剩余的敲击次数n。
算法基于这样一个事实，最优按键序列一定只有两种情况：当N较小时，一直按A肯定最优，因为C-A、C-V要两个操作数，比A一个操作数代价高；当N较大时，
A,A,…C-A,C-C,C-V,C-V的形式肯定最好，因为N很多，后期C-V的收获肯定很大。综上，最后一次按键要么是A要么是C-V通过上述所述，可以通过这两种情况来设计算法：
// 定义dp数组，dp数组定义为：dp[i]为使用了i个操作数后，最多显示dp[i]个A int[] dp = new int[N + 1]; // 遍历状态 for (int i = 0; i <= N; i++) dp[i] = max( 这次按 A 键， 这次按 C-V )对于「按A键」这种情况，就是状态i - 1的屏幕上新增了一个 A 而已，很容易得到结果：
// 按 A 键，就比上次多一个 A 而已 dp[i] = dp[i - 1] + 1;
对于[AAAC-AC-VC-V...]的情况，我们用一个变量j作为若干C-V的起点。那么j之前的 2 个操作就应该是C-A C-C了：
for (int j = 2; j < i; j++) { // C-A和C-C占用两个操作数，因此第一个C-V前，共有最多dp[j-2]个A // 连续C-V共i-j次，因此屏幕上此时共有dp[j-2]+(i-j)*dp[j-2]个A即dp[j-2]*(i-j+1)个A dp[i] = Math.max(dp[i], dp[j - 2] * (i - j + 1)); }综上，算法整体就为：
// 定义dp数组，dp数组定义为：dp[i]为使用了i个操作数后，最多显示dp[i]个A int[] dp = new int[N + 1]; // 遍历状态 for (int i = 0; i <= N; i++) { // 按 A 键，就比上次多一个 A 而已 dp[i] = dp[i - 1] + 1; // 按A...C-AC-CC-V... for (int j = 2; j < i; j++) { // C-A和C-C占用两个操作数，因此第一个C-V前，共有最多dp[j-2]个A // 连续C-V共i-j次，因此屏幕上此时共有dp[j-2]+(i-j)*dp[j-2]个A即dp[j-2]*(i-j+1)个A dp[i] = Math.max(dp[i], dp[j - 2] * (i - j + 1)); } } // 返回结果 return dp[N];
京公网安备 11010502036488号