【42页动态规划学习笔记分享】动态规划核心原理详解及27道LeetCode相关经典题目汇总（4）

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        n = len(nums)
        if n == 0:
            return 0
        dpMax = [float('-inf')] * n  # 存储以i结尾的最大连续子数组乘积
        dpMax[0] = nums[0]
        dpMin = [float('inf')] * n # 存储以i结尾的最小连续子数组乘积，存在负负得正的情况
        dpMin[0] = nums[0]
        for i in range(1,n):
            dpMax[i] = max(dpMin[i - 1] * nums[i], dpMax[i - 1] * nums[i], nums[i])
            dpMin[i] = min(dpMin[i - 1] * nums[i], dpMax[i - 1] * nums[i], nums[i])
        return max(dpMax)

class Solution:
    def rob(self, nums: List[int]) -> int:
        #dp[i] 表示前 i间房屋能偷窃到的最高总金额
        #dp[i] = max(dp[i-1],dp[i-2]+nums[i]) 
        n = len(nums)
        if n==0:
            return 0
        if n==1:
            return nums[0]
        dp = [0]* n
        dp[0] = nums[0]
        dp[1] = max(nums[0],nums[1])
        for i in range(2,n):
            dp[i] = max(dp[i-1],dp[i-2]+nums[i])
        return dp[n-1]

class Solution:
def minPathSum(self, grid: List[List[int]]) -> int:
    # dp[i][j]表示达到i,j点的最小路径和
        m = len(grid)
        n = len(grid[0])
        dp = [[0]*n for _ in range(m)]
        dp[0][0] = grid[0][0]
        for i in range(1, m):
            dp[i][0] = dp[i-1][0] + grid[i][0]
        for i in range(1, n):
            dp[0][i] = dp[0][i-1] + grid[0][i]
        for i in range(1, m):
            for j in range(1, n):
                dp[i][j] = min(dp[i][j-1], dp[i-1][j]) + grid[i][j]
        return dp[-1][-1]

# 动态规划
 class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        # 动态规划dp[i] 表示前 i 天的最大利润
        n = len(prices)
        if n == 0: return 0 # 边界条件
        dp = [0] * n
        minprice = prices[0]
        for i in range(1, n):
            minprice = min(minprice, prices[i])
            dp[i] = max(dp[i - 1], prices[i] - minprice)
        return dp[-1]
                  
# 方法二
def maxProfit(self, prices: List[int]) -> int:
    minprice = float('inf') # 正无穷  负无穷 float("-inf")
    maxprofit = 0
    for p in prices:
        minprice = min(minprice, p)
        maxprofit = max(maxprofit, p-minprice)
    return maxprofit

def maxProfit(self, prices: List[int]) -> int:
    #在第二次买的时候，价格其实是考虑用了第一次赚的钱去补贴一部分的
    buy_1 = buy_2 = float('inf') # 第一二次买之前的最低价
    pro_1 = pro_2 = 0
   
    for p in prices:
        buy_1 = min(buy_1, p)
        pro_1 = max(pro_1, p - buy_1)
        buy_2 = min(buy_2, p - pro_1) # p - pro_1 是用第一次的钱抵消了一部分第二次买的钱
        pro_2 = max(pro_2, p - buy_2)
    return pro_2

class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        # 踏上第i级台阶的最小花费，用dp[i]表示
        # 初始条件：
        # 最后一步踏上第0级台阶，最小花费dp[0] = cost[0]。
        # 最后一步踏上第1级台阶有两个选择：
        # 可以分别踏上第0级与第1级台阶，花费cost[0] + cost[1]；
        # 也可以从地面开始迈两步直接踏上第1级台阶，花费cost[1]。
        n = len(cost)
        dp = [0] * n
        dp[0], dp[1] = cost[0], cost[1]
        for i in range(2, n):
            dp[i] = min(dp[i - 2], dp[i - 1]) + cost[i]
        return min(dp[-2], dp[-1])

class Solution:
    def numDecodings(self, s: str) -> int:
        if s[0] == '0':
            return 0
        n = len(s)
        dp = [0] * (n + 1)
        dp[0] = 1
        dp[-1] = 1
        for i in range(1,n):
            # '0'只有10和20才有对应字母，不然 返回 0        
            if s[i] == '0':
                if s[i-1]=='1' or s[i-1]=='2':
                    dp[i] = dp[i-2]
                else:
                    return 0
            else:
                if s[i-1] == '1' or (s[i-1] =='2' and s[i] < '7'):
                    # i-1与i 可以结合或者分开
                    dp[i] = dp[i-1] + dp[i-2]
                else:
                    # i-1与i 必须分开
                    dp[i] = dp[i-1]
        return dp[-2]

# 动态规划 DP
class Solution(object):
    def racecar(self, target):
        # dp[x] 表示到达位置 x 的最短指令长度
        dp = [0, 1] + [float('inf')] * target
        for t in range(2, target + 1):
            k = t.bit_length()
            if t == 2**k - 1:
                dp[t] = k
                continue
            for j in range(k - 1):
                # t - (2**(k-1)-2**j) 为剩余距离，dp[t - 2**(k - 1) + 2**j]表示这个剩余距离需要使用的最少命令数,加上已经使用的 k - 1 + j + 2
                # 由于返回使用的j不确定，因此需要通过遍历【0，k-2】确定dp[t]的最小值        
                dp[t] = min(dp[t], dp[t - 2**(k - 1) + 2**j] + k - 1 + j + 2)
            # 2**k - 1 - t 表示剩余需要按返回的距离，dp[2**k - 1 - t]表示走剩余距离需要要使用的最少命令数，加上已经使用的k+1
            dp[t] = min(dp[t], dp[2**k - 1 - t] + k + 1)
        return dp[target]
                  
# 递归写法
class Solution:
    dp = {0: 0}
    def racecar(self, target: int) -> int:
        t = target
        if t in self.dp:
            return self.dp[t]
        n = t.bit_length()
        if 2**n - 1 == t:
            self.dp[t] = n
        else:
            self.dp[t] = self.racecar(2**n - 1 - t) + n + 1
            for m in range(n - 1):
                self.dp[t] = min(self.dp[t], self.racecar(t - 2**(n - 1) + 2**m) + n + m + 1)
        return self.dp[t]

class Solution:
    def numMusicPlaylists(self, N: int, L: int, K: int) -> int:
        mod = 10 ** 9 + 7
        # dp[i][j] 表示用j首不同的歌填充长度为i的歌单数目
        dp = [[0] * (N + 1) for _ in range(L + 1)]
        dp[0][0] = 1
        for i in range(1, L + 1):
            for j in range(1, N + 1):
                # 分成两种情况，我们可以播放没有播放过的歌也可以是播放过的
                # 如果当前的歌和前面的都不一样，歌单前i-1首歌只包括了j-1首不同的歌曲，
                # 那么当前的选择有dp[i-1][j-1] * (N-j+1)
                # 如果不是，那么就是选择之前的一首歌，之前最近的K首是不能选的，只能选择j-K前面的歌曲，（j 首歌，最近的 K 首不可以播放）
                # 所以选择就是dp[i-1][j] * max(0, j-K)        
                dp[i][j] = (dp[i-1][j-1] * (N - j + 1) + dp[i-1][j] * max(0, j - K)) % mod
        return dp[-1][-1]