【42页动态规划学习笔记分享】动态规划核心原理详解及27道LeetCode相关经典题目汇总（3）https://developer.aliyun.com/article/1536620
乘积最大子数组
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
买卖股票的最佳时机2
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]
