309号问题
来源：9-4 状态的定义和状态转移 House Robber
湿地车手
2021-10-06
bobo老师我不知道为什么309号问题我这种思路就一直超时，
我把状态定义为【第i天买入能获得的最大利润值】
然后就开始递归
public int maxProfit(int[] prices) {
if(prices.length <= 1) return 0;
if(prices.length == 2) return Math.max(0, prices[1] - prices[0]);
int[] maxP = new int[prices.length];
Arrays.fill(maxP, -1);
int max = 0;
// 分别计算从第0天买入到第n-1天买入的最大值，最终得到最大的那个结果返回
for(int i = 0; i < prices.length && maxP[i] == -1; i++) {
max = Math.max(max, getMaxProfit(i, prices, maxP));
}
return max;
}
private int getMaxProfit(int buyIndex, int[] prices, int[] maxP) {
// 先计算prices的最后一天的index
int lastDayIndex = prices.length - 1;
// 如果当天的index已经大于等于最后一天的index，那么就不能买入直接返回0
if(buyIndex >= lastDayIndex) {
return 0;
}
// 如果当天的最大值已经计算过，就直接返回
if(maxP[buyIndex] != -1) return maxP[buyIndex];
// 如果当天的最大值没有计算过，就开始计算
int res = 0;
// 开始遍历能够卖出的日期，从buyIndex + 1开始才能卖
for(int sellIndex = buyIndex + 1; sellIndex <= lastDayIndex; sellIndex++) {
// 如果sellIndex这天卖掉了，得到当前的profit
int profit = prices[sellIndex] - prices[buyIndex];
// 如果profit < 0 说明卖的不合理，直接跳过后面所有
if(profit <= 0) continue;
// 否则就是可以卖掉了，并开始循环cooldown期的长度，决定下一次买入的index
for(int coolDown = 2; coolDown + sellIndex <= lastDayIndex + 2; coolDown++) {
// 获得经过当前cooldown期再次买入能够获得的最大利润
int curRes = profit + getMaxProfit(sellIndex + coolDown, prices, maxP);
// 选出最大的
res = Math.max(res, curRes);
}
}
// 记忆结果并返回
return maxP[buyIndex] = res;
}
用一个maxP[i]的数组去记录得到的第i天买入能获得的最大利润，然后分别计算从第0天买入到第n-1天买入的最大值，最终得到最大的那个结果返回。
虽然看起来要计算的步骤很多，但是其实当
for(int i = 0; i < prices.length && maxP[i] == -1; i++) {
max = Math.max(max, getMaxProfit(i, prices, maxP));
}
中的i = 0代入得到结果的时候，maxP[]大部分的值就已经都算出了，后面只要遇到maxP[i] != -1的情况时候直接就可以得到最大值，所以最后的复杂度是N + N^2?这不就是常规记忆化搜索的时间复杂度吗。。。为什么一直超时呢？
老师可以稍微花点时间看一下我的代码吗，我这个思路真的想不明白为什么会超时，我注释全写在上面了谢谢谢谢。。
1回答
-
你的逻辑没有问题。你的代码之所以超时，就是因为对于这个问题的数据量，O(n^2) 的算法就是会超时的。这个问题有 O(n) 的算法。
你的叙述里最大的问题是，“这不就是常规记忆化搜索的时间复杂度吗”。记忆化搜索没有常规的复杂度，没有任何一条规定说记忆化搜索一定是 O(n^2) 的，也没有任何一条规定说，O(n^2) 的记忆化搜索不会超时。
其实根据你的代码，可以很容易的修改成 O(n) 的算法。状态定义稍微变一下。你的状态定义表示，buyIndex 一定会买入。我下面的代码中，startIndex 表示，从 startIndex 那一天开始可以操作（但也可以不操作。）请仔细理解这两种状态定义的不同，以及根据状态定义的不同，产生的逻辑差异。（而实际上，你的代码注释虽然很完善，却唯独没有对你对状态的定义到底是什么？这一点在做 dp 的时候，是至关重要的。）
另外要引入的一个新的状态，是操作是“买”还是“卖”，对应我的递归函数中的 op，可以选择 BUY 和 SELL 两种（对应 0 和 1）。买完以后必须卖，卖完以后必须买。
所以，我的 getMaxProfit(op, startIndex) 表示的是，在 startIndex 这一天开始，可以做 op 动作的最大利润（注意是“可以”，不是“必须”。）
class Solution { private int BUY = 0, SELL = 1; public int maxProfit(int[] prices) { if(prices.length <= 1) return 0; if(prices.length == 2) return Math.max(0, prices[1] - prices[0]); int[][] maxP = new int[2][prices.length]; for(int i = 0; i < 2; i ++) Arrays.fill(maxP[i], Integer.MIN_VALUE); // 在我的状态定义下，直接返回 startIndex = 0 可以 BUY 的结果就好，不需要循环 // 想想为什么？ return getMaxProfit(BUY, 0, prices, maxP); } private int getMaxProfit(int op, int startIndex, int[] prices, int[][] maxP) { // 先计算prices的最后一天的index int lastDayIndex = prices.length - 1; if(startIndex > lastDayIndex) return 0; // 如果是 SELL，在最后一天，只能 sell 出去 if(startIndex == lastDayIndex) return op == BUY ? 0 : prices[startIndex]; // 如果当天的最大值已经计算过，就直接返回 if(maxP[op][startIndex] != Integer.MIN_VALUE) return maxP[op][startIndex]; // 如果当天的最大值没有计算过，就开始计算 int res = 0; if(op == BUY){ // 可以在这一天买 res = -prices[startIndex] + getMaxProfit(SELL, startIndex + 1, prices, maxP); // 也可以这一天不买，后续再买 res = Math.max(res, getMaxProfit(BUY, startIndex + 1, prices, maxP)); } else{ // 可以这一天卖，但注意，因为 cool down，所以卖完以后，下一次买的最早时间是 startIndex + 2 res = prices[startIndex] + getMaxProfit(BUY, startIndex + 2, prices, maxP); // 也可以这一天不卖，后续再卖 res = Math.max(res, getMaxProfit(SELL, startIndex + 1, prices, maxP)); } return maxP[op][startIndex] = res; } }看看上面的逻辑你是否可以看懂？有问题可以继续追问。
继续加油！：）
032021-10-10
相似问题