买卖股票 | House Robber

Best Time to buy and sell stocks

参考labladong大神的帖子

买卖股票是一个系列问题，「状态」有三个，第一个是天数，第二个是允许交易的最大次数，第三个是当前的持有状态（即之前说的 rest 的状态，我们不妨用 1 表示持有，0 表示没有持有）。然后我们用一个三维数组就可以装下这几种状态的全部组合：

dp[i][k][0 or 1]
0 <= i <= n-1, 1 <= k <= K
n 为天数，大 K 为最多交易数
此问题共 n × K × 2 种状态，全部穷举就能搞定。

for 0 <= i < n:
    for 1 <= k <= K:
        for s in {0, 1}:
            dp[i][k][s] = max(buy, sell, rest)

• dp[3][2][1] 的含义就是：今天是第三天，我现在手上持有着股票，至今最多进行 2 次交易。

• dp[2][3][0] 的含义：今天是第二天，我现在手上没有持有股票，至今最多进行 3 次交易。

我们想求的最终答案是 dp[n - 1][K][0]，即最后一天，最多允许 K 次交易，最多获得多少利润。读者可能问为什么不是 dp[n - 1][K][1]？因为 [1] 代表手上还持有股票，[0] 表示手上的股票已经卖出去了，很显然后者得到的利润一定大于前者。

二、状态转移框架

现在，我们完成了「状态」的穷举，我们开始思考每种「状态」有哪些「选择」，应该如何更新「状态」。只看「持有状态」，可以画个状态转移图。

Best Time to Buy and Sell Stock IV

• at most K transaction

• 最general的股票买卖题目

• f[i][k][0 or 1] represents max profit after day i and making at most K transaction with state j, j can be 0 or 1, 1 means hold

class Solution {
    /*
    股票交易通用模板
    f[i][k][0 or 1] represents max profit after day i and making at most K transaction with state j, j can be 0 or 1, 1 means hold
    base: 
    f[0][k][0] = 0
    f[0][k][1] = 0
    
    state:
    f[i][k][0] = max(f[i-1][k][0], f[i-1][k][1] + prices[i]) //max(rest, sell)
    f[i][k][1] = max(f[i-1][k][1], f[i-1][k - 1][0] - prices[i]) //max(rest, buy)
    
    res: f[n-1][k][0]
    
    这题还需要compare k with len/2
    if k > len / 2, 就相当于是infininte transactions
    whenver prices[i] - prices[i - 1] >0, then add to profit
    */
    public int maxProfit(int k, int[] prices) {
        int n = prices.length;
        if (n < 2 || k == 0 ) return 0;
        if (k > n / 2) {
            return maxProfitWithInfiniteK(prices);
        }
        int[][][] dp = new int[n][k + 1][2];
        //initialization
        for (int j = 0; j <= k; j++) {
            dp[0][j][0] = 0;
            dp[0][j][1] = -prices[0];
        }
        for (int i = 1; i < n; i++) {
            for (int j = 1; j <=k; j++) {
                dp[i][j][0] = Math.max(dp[i - 1][j][0], dp[i - 1][j][1] + prices[i]);
                dp[i][j][1] = Math.max(dp[i - 1][j][1], dp[i - 1][j - 1][0] - prices[i]);
            }
        }
        return dp[n-1][k][0];
    }
    private int maxProfitWithInfiniteK(int[] prices) {
        int maxProfit = 0;
        for (int i = 1; i < prices.length;i ++) {
            maxProfit += Math.max(0, prices[i]-  prices[i - 1]);
        }
        return maxProfit;
    }
}

Best Time to Buy and Sell Stock III

• K=2的情况，套用IV模板就好

Best Time to Buy and Sell Stock I

• At most one transaction, 即K = 1的情况

• f[i][0] = max(f[i-1][0], f[i-1][1] + prices[i])

• f[i][1] = max(f[i-1][1], - prices[i]) //注意，不是max(f[i-1][1], f[i-1][0] - prices[i])

class Solution {
    /*
    简易解法
    K = 1 transaction
    keep track of minPrice and maxProfit
    */
    public int maxProfit(int[] prices) {
        int minPrice = Integer.MAX_VALUE;
        int maxProfit = 0;
        for (int i = 0; i < prices.length; i++) {
            if (prices[i] < minPrice) {
                minPrice = prices[i];
            } else if (prices[i] - minPrice > maxProfit) {
                maxProfit = prices[i] - minPrice;
            }
        }
        return maxProfit;
    }
}

class Solution {
    /*
    股票交易通用模板，第4题最general:
    f[i][k][0 or 1] 前i天交易K次后在状态j时的max profit, j can be 0 or 1, 1 means hold
    base: depends
    res: f[n-1][k][0]

    此题即为k = 1的特殊情况
    f[i][0] = max(f[i-1][0], f[i-1][1] + prices[i])
    f[i][1] = max(f[i-1][1], - prices[i]) //注意，不是max(f[i-1][1], f[i-1][0] - prices[i]) 因为只能交易一次
    
    initial:
    f[0][0] = 0, f[0][1] = -prices[0]
    res:
    f[n - 1][0]
    
    */
    public int maxProfit(int[] prices) {
        int n = prices.length;
        if (n < 2) return 0;
        int[][] f = new int[n][2];
        //initialization
        f[0][0] = 0;
        f[0][1] = -prices[0];

        for (int i = 1; i < n; i++) {
            f[i][0] = Math.max(f[i-1][0], f[i-1][1] + prices[i]);
            f[i][1] = Math.max(f[i-1][1], - prices[i]);
        }
        return f[n - 1][0];
    }
}

Best Time to Buy and Sell Stock II

• K= infinite的情况

• 这题可以用Greedy贪心来做

• whenever prices[i] - prices[i - 1] >0, then add to profit

public int maxProfit(int[] prices) {
        int n = prices.length;
        if (n < 2) return 0;
        int maxProfit = 0;
        for (int i = 1; i < n;i ++) {
            maxProfit += Math.max(0, prices[i]-  prices[i - 1]);
        }
        return maxProfit;
    }

Best Time to Buy and Sell Stock with Cooldown

• 带冷却时间的情况

• K = Infinite

class Solution {
    /*
    股票交易通用模板
    f[i][k][0 or 1] represents max profit after day i and making at most K transaction with state j, j can be 0 or 1, 1 means hold
    base: 
    f[0][0] = 0
    f[0][1] = -prices[0]
    f[1][0] = max(f[0][0], f[0][1] + prices[1])
    f[1][1] = max(f[0][1], -prices[1])
    
    state:
    f[i][0] = max(f[i-1][0], f[i-1][1] + prices[i]) //max(rest, sell)
    f[i][1] = max(f[i-1][1], f[i-2][0] - prices[i]) //max(rest, buy)
    
    res: f[n-1][0]
    */
    public int maxProfit(int[] prices) {
        int n = prices.length;
        if ( n < 2) return 0;
        int[][] f = new int[n][2];
        //initialization
        f[0][0] = 0;
        f[0][1] = -prices[0];
        f[1][0] =  Math.max(f[0][0], f[0][1] + prices[1]);
        f[1][1] = Math.max(f[0][1], -prices[1]);
        for (int i = 2; i < n; i++) {
            f[i][0] = Math.max(f[i - 1][0], f[i - 1][1] + prices[i]);
            f[i][1] = Math.max(f[i - 1][1], f[i - 2][0] - prices[i]);
        }
        return f[n - 1][0];
    }
}

Best Time to Buy and Sell Stock with Transaction Fee

• 带交易费的情况

• K = Infinite

class Solution {
    /*
    股票交易通用模板
    f[i][k][0 or 1] represents max profit after day i and making at most K transaction with state j, j can be 0 or 1, 1 means hold
    base: 
    f[0][0] = 0
    f[0][1] = -prices[0]

    
    state:
    f[i][0] = max(f[i-1][0], f[i-1][1] + prices[i] - fee) //max(rest, sell)
    f[i][1] = max(f[i-1][1], f[i-1][0] - prices[i]) //max(rest, buy)
    
    res: f[n-1][0]
    */
    public int maxProfit(int[] prices, int fee) {
        int n = prices.length;
        if (n < 2) return 0;
        int[][] f = new int[n][2];
        //initialization
        f[0][0] = 0;
        f[0][1] = -prices[0];
        for (int i = 1; i < n; i++) {
            f[i][0] = Math.max(f[i - 1][0], f[i - 1][1] + prices[i] - fee);
            f[i][1] = Math.max(f[i - 1][1], f[i - 1][0] - prices[i]);
        }
        return f[n - 1][0];
    }
}

House Robber

• 相邻两家不能同时抢

class Solution {
    /*
    f[i] means max until first i houses
    f[i] = max(f[i - 1], f[i - 2] + nums[i - 1])
    res: f[n]
    f[0] = 0
    f[1] = nums[0]
    
    */
    public int rob(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        int n = nums.length;
        int[] f = new int[n + 1];
        f[0] = 0; 
        f[1] = nums[0];
        for (int i = 2; i <= n; i++) {
            f[i] = Math.max(f[i - 1], f[i - 2] + nums[i - 1]);
        }
        return f[n];
    }
    //rolling array to optimize for O(1) space, 2 var
    public int rob(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        int n = nums.length;
        int include = 0, exclude = 0;
        for (int i = 0; i < n; i++) {
            int in = include, ex = exclude;
            include = ex + nums[i];
            exclude = Math.max(ex, in);
        }
        return Math.max(include, exclude);
    }
}

House Robber II

• 收尾相连

• 所以针对收尾的两个房子有3种情况

  • both nums[0] and nums[n - 1] not rob

  • rob nums[0] only, not nums[n - 1]

  • rob nums[n - 1] only, not nums[0]

• 不用考虑第1种情况，因为结果可以被2,3 cover

• 可以转化为区间型 DP -> rob(int[] nums, int begin, int end)

class Solution {
    /*
    3 scenario:
    1.both nums[0] and nums[n - 1] not rob
    2.rob nums[0] only, not nums[n - 1]
    3.rob nums[n - 1] only, not nums[0]
    不用考虑第1种情况，因为结果可以被2,3 cover
    区间型 DP -> rob(int[] nums, int begin, int end)
    */
    public int rob(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        if (nums.length == 1) return nums[0];
        int n = nums.length;
        return Math.max(rob(nums, 0, n - 2), rob(nums, 1, n - 1));
    }
    private int rob(int[] nums, int begin, int end) {
        int n = nums.length;
        int exclude = 0, include = 0;
        for (int i = begin; i <= end; i++) {
            int in = include, ex = exclude;
            include = ex + nums[i];
            exclude = Math.max(in, ex);
        }
        return Math.max(include, exclude);
    }
}

House Robber III

• 抢劫的路径改为binary tree

• 这个反而更简单了，divide & conquer返回resultType

• Tree DFS traverse不需要memo, 因为没有重复计算可以优化

class Solution {
    /*
    Tree traverse不需要memo, 因为没有重复计算可以优化
    */
    public int rob(TreeNode root) {
        if (root == null) return 0;
        int[] res = dp(root);
        return Math.max(res[0], res[1]);
    }
    //res[0] max with root
    //res[1] max without root
    private int[] dp(TreeNode root) {
        if (root == null) {
            return new int[]{0,0};
        }
        int[] left = dp(root.left);
        int[] right = dp(root.right);
        int[] res = new int[2];
        res[0] = root.val + left[1] + right[1];
        res[1] = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
        return res;
    }
}