LeetCode-DP

[MiaoRain]

class Solution:
    def rob(self, nums: List[int]) -> int:
        #dp[i] = Max((dp[i-2]+A), dp[i-1])
        n = len(nums) 
        if n == 0:
            return 0
        dp = [0] * (n + 1)
        dp[0] = 0
        dp[1] = nums[0]
        for i in range(2, n+1):
                dp[i] = max(dp[i-2] + nums[i-1], dp[i-1])
        return dp[-1]

[MiaoRain]

class Solution:
    def rob(self, nums: List[int]) -> int:
        #去头掐尾各调一次dp[i] = Max((dp[i-2]+A), dp[i-1]) 
        def main(nums):
            n = len(nums) 
            if n == 0:
                return 0
            dp = [0] * (n + 1)
            dp[0] = 0
            dp[1] = nums[0]
            for i in range(2, n+1):
                    dp[i] = max(dp[i-2] + nums[i-1], dp[i-1])
            return dp[-1]

        n = len(nums) 
        if n == 0:
            return 0
        if n == 1:
            return nums[0]
        if n == 2: return max(nums[0], nums[1])
        return max(main(nums[1:]), main(nums[:-1]))

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def rob(self, root: TreeNode) -> int:
        return self.helper(root)[1]
    # helper函数返回一个节点为根的最大值 = [当前节点不参与计算的最大收益，当前节点的最大收益(参与/不参与)]
    def helper(self, root):
        if root is None:
            return [0, 0]
        left_amount = self.helper(root.left)
        right_amount = self.helper(root.right)
        withoutRoot = left_amount[1] + right_amount[1]
        withRoot = root.val + left_amount[0] + right_amount[0]
        return [withoutRoot, max(withRoot, withoutRoot)]

#链接：https://leetcode-cn.com/problems/house-robber-iii/solution/dpdi-gui-qiu-jie-by-oliver8641/

[MiaoRain]

https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iv/solution/gu-piao-jiao-yi-xi-lie-cong-tan-xin-dao-dong-tai-g/ @labuladong python版

# 简化版
        n = len(prices)
        dp_i_0 = 0
        dp_i_1 = float('-inf')
        for i in range(n):
            dp_i_0 = max(dp_i_0, dp_i_1 + prices[i])
            dp_i_1 = max(dp_i_1, -prices[i])
            #print(dp_i_1)
        return dp_i_0

        """
        #k = 1 完全版
        n = len(prices)
        if n == 0:
            return 0
        dp = [[0] * 2 for _ in range(n)]
        for i in range(n):
            if (i - 1)== -1:
                dp[i][0] = 0;
                #// 解释：
                #// dp[i][0] 
                #// = max(dp[-1][0], dp[-1][1] + prices[i])
                #// = max(0, -infinity + prices[i]) = 0
                dp[i][1] = -prices[i];
                #//解释：
                #// dp[i][1] 
                #// = max(dp[-1][1], dp[-1][0] - prices[i])
                #// = max(-infinity, 0 - prices[i]) 
                #// = -prices[i]
                continue
            dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i]) 
            dp[i][1] = max(dp[i-1][1], - prices[i])
        print(dp)
        return dp[n-1][0]
        """

[MiaoRain]

        # 简化版
        n = len(prices)
        dp_i_0 = 0
        dp_i_1 = float('-inf')
        for i in range(n):
            dp_i_0 = max(dp_i_0, dp_i_1 + prices[i])
            dp_i_1 = max(dp_i_1, dp_i_0 - prices[i])
            #print(dp_i_1)
        return dp_i_0

        """
        #k = n
        n = len(prices)
        if n == 0:
            return 0
        dp = [[0] * 2 for _ in range(n)]
        #print(dp)
        #dp[-1][0] = dp[n-1]
        for i in range(n):
            if (i - 1)== -1:
                dp[i][0] = 0;
                #// 解释：
                #//   dp[i][0] 
                #// = max(dp[-1][0], dp[-1][1] + prices[i])
                #// = max(0, -infinity + prices[i]) = 0
                dp[i][1] = -prices[i];
                #//解释：
                #//   dp[i][1] 
                #// = max(dp[-1][1], dp[-1][0] - prices[i])
                #// = max(-infinity, 0 - prices[i]) 
                #// = -prices[i]
                continue
            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])
        print(dp)
        return dp[n-1][0]
        """

[MiaoRain]

# 简化版dp_i20 i指第天，2指最多允许2次交易操作，0是手头没有股票
        n = len(prices)
        dp_i10, dp_i11 = 0, float('-inf') #float('-inf')负无穷表示不可能
        dp_i20, dp_i21 = 0, float('-inf')
        for i in range(n):
            dp_i20 = max(dp_i20, dp_i21 + prices[i]);
            dp_i21 = max(dp_i21, dp_i10 - prices[i]);
            dp_i10 = max(dp_i10, dp_i11 + prices[i]);
            dp_i11 = max(dp_i11, -prices[i]);
        return dp_i20

[MiaoRain]

class Solution:
    def maxProfit(self, k, prices: List[int]) -> int:
        n = len(prices)
        if n <= 1: return 0

        if k >= n//2:   # 退化为不限制交易次数
            profit = 0
            for i in range(1, n):
                if prices[i] > prices[i - 1]:
                    profit += prices[i] - prices[i - 1]
            return profit

        else:           # 限制交易次数为k
            dp = [[[None, None] for _ in range(k+1)] for _ in range(n)]  # (n, k+1, 2)
            for i in range(n):
                dp[i][0][0] = 0
                dp[i][0][1] = -float('inf')
            for j in range(1, k+1):
                dp[0][j][0] = 0
                dp[0][j][1] = -prices[0]
            for i in range(1, n):
                for j in range(1, k+1):
                    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 dp[-1][-1][0]

#链接：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iv/solution/gu-piao-jiao-yi-xi-lie-cong-tan-xin-dao-dong-tai-g/

[MiaoRain]

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        # 简化版
        n = len(prices)
        dp_i_0 = 0
        dp_i_1 = float('-inf')
        dp_pre_0 = 0 #代表dp[i-2][0]
        for i in range(n):
            temp = dp_i_0
            dp_i_0 = max(dp_i_0, dp_i_1 + prices[i])
            dp_i_1 = max(dp_i_1, dp_pre_0 - prices[i])
            dp_pre_0 = temp
            #print(dp_i_1)
        return dp_i_0

[MiaoRain]

class Solution:
    def maxProfit(self, prices: List[int], fee: int) -> int:
                # 简化版
        n = len(prices)
        dp_i_0 = 0
        dp_i_1 = float('-inf')
        dp_pre_0 = 0 #代表dp[i-2][0]
        for i in range(n):
            temp = dp_i_0
            dp_i_0 = max(dp_i_0, dp_i_1 + prices[i])
            dp_i_1 = max(dp_i_1, temp - prices[i] - fee)

            #print(dp_i_1)
        return dp_i_0