Python题解Leetcode Hot100之动态规划

动态规划解题步骤-5部曲

1. 确定dp数组（dp table）以及下标的含义
2. 确定递推公式
3. dp数组如何初始化
4. 确定遍历顺序
5. 举例推导dp数组

70. 爬楼梯

题目描述

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶？

解题思路

f(n) = f(n-2) + f(n-1)

Python代码

class Solution:def climbStairs(self, n: int) -> int:n_1 = n_2 = 1if n <=1:return 1for i in range(2, n+1):f_n = n_1 + n_2n_2 = n_1n_1 = f_nreturn f_n

---

118. 杨辉三角

题目描述

给定一个非负整数 numRows，生成杨辉三角的前 numRows 行。

解题思路

杨辉三角的每个元素是上一行左右两个元素之和，边界元素为 1。用一个二维列表来存储结果，每行第一个和最后一个元素固定为 1，其他元素是它左上和右上的和。

Python代码

class Solution:def generate(self, numRows: int) -> List[List[int]]:if numRows == 0:return []res = [[1]]if numRows == 1:return resres.append([1, 1])if numRows == 2:return resfor i in range(3, numRows+1):last_nums = res[-1] cur_nums = [1]numRows = len(last_nums)for j in range(numRows-1):cur_nums.append(last_nums[j]+last_nums[j+1])cur_nums.append(1)res.append(cur_nums)return res

---

198. 打家劫舍

题目描述

你是一个专业的窃贼，计划偷窃沿街的房屋。每间房内都藏有一定的现金，如果相邻的两间房屋在同一晚上被小偷闯入，系统会自动报警。给定一个代表每个房屋存放金额的非负整数数组，计算你不触动报警装置的情况下，今晚能够偷窃到的最高金额。

解题思路

使用动态规划来解决。假设 dp[i] 表示前 i 间房屋所能偷窃的最高金额，则状态转移方程为 dp[i] = max(dp[i-1], dp[i-2] + nums[i])，初始条件为 dp[0] = nums[0] 和 dp[1] = max(nums[0], nums[1])。

Python代码

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

---

279. 完全平方数

题目描述

给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。

解题思路

使用动态规划来解决。假设 dp[i] 表示组成整数 i 所需要的最少的完全平方数的数量，则状态转移方程为 dp[i] = min(dp[i - 1* 1] + 1，dp[i - 2 * 2] + 1，... , dp[i - j * j] + 1)，其中 j * j 是当前平方数，由此来更新每一个 dp 位置。
求和问题

Python代码

class Solution:def numSquares(self, n: int) -> int:dp = [0] * (n + 1)dp[1] = 1for i in range(2, n + 1):j = 1res = float('inf')while j * j <= i:res = min(res, dp[i - j * j] + 1)j += 1dp[i] = resreturn dp[n]

---

322. 零钱兑换

题目描述

给定不同面额的硬币和一个总金额。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。

解题思路

完全背包问题：
背包容量：总金额
物品重量：硬币价值
物品价值：数量

假设 dp[i] 表示金额 i 所需的最小硬币数，则状态转移方程为 dp[i] = min(dp[i], dp[i - coin] + 1)，其中 coin 是可选的硬币面值。

完全背包的物品可以被取无数次，因此完全背包的内循环为正序，当前物品可以被重复取用；

Python代码

class Solution:def coinChange(self, coins: List[int], amount: int) -> int:n = len(coins)dp = [float("inf")] * (amount + 1)dp[0] = 0for i in range(1, amount + 1):if i % coins[0] == 0:dp[i] = i // coins[0]for i in range(1, n):for j in range(coins[i], amount + 1):dp[j] = min(dp[j], dp[j-coins[i]] + 1)return -1 if dp[amount] == float("inf") else dp[amount]

---

139. 单词拆分

题目描述

给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。
输入: s = “applepenapple”, wordDict = [“apple”, “pen”]
输出: true

解题思路

可以转化成完全背包问题，而且是排列问题，字符串s是背包，字符串列表里的字符是物品； dp[i] 表示前 i 个字符是否能被拆分; 因为是排列问题，所以外循环遍历背包，内循环遍历物品；

Python代码

class Solution:def wordBreak(self, s: str, wordDict: List[str]) -> bool:n = len(s)word_n = len(wordDict)dp = [False] * (n + 1)dp[0] = Truefor j in range(1, n+1):for i in range(word_n):if j >= len(wordDict[i]):dp[j] = (dp[j] or (s[j - len(wordDict[i]):j] == wordDict[i] and dp[j-len(wordDict[i])]))# print(dp)return dp[n]

---

300. 最长递增子序列

题目描述

给定一个无序的整数数组，找到其中最长递增子序列的长度。

解题思路

使用动态规划来解决。假设 dp[i] 表示以 nums[i] 结尾的最长递增子序列的长度，则状态转移方程为：dp[i] = max(dp[j] + 1)，其中 j 从 0 到 i-1 且 nums[j] < nums[i]。

Python代码

class Solution:def lengthOfLIS(self, nums: List[int]) -> int:n = len(nums)dp = [1] * nres = 1for i in range(1, n):for j in range(i):if nums[j] < nums[i]:dp[i] = max(dp[i], dp[j] + 1)res = max(res, dp[i])return res

---

152. 乘积最大子数组

题目描述

给你一个整数数组 nums ，请你找出数组中乘积最大的连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。
输入: nums = [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6。

解题思路

使用动态规划来解决。维护两个变量 max_val 和 min_val，表示以当前元素为结尾的子数组的最大乘积和最小乘积，然后遍历数组更新这两个值。

Python代码

class Solution:def maxProduct(self, nums: List[int]) -> int:if not nums:return 0max_val = min_val = res = nums[0]for i in range(1, len(nums)):if nums[i] < 0:max_val, min_val = min_val, max_valmax_val = max(nums[i], max_val * nums[i])min_val = min(nums[i], min_val * nums[i])res = max(res, max_val)return res

---

416. 分割等和子集

题目描述

给定一个只包含正整数的非空数组，判断是否可以将这些数字分成两个子集，使得两个子集的元素和相等。

解题思路

转换0，1背包问题，判断是否能找到一个子集，其和等于总和的一半。01背包问题，内循环反向遍历

Python代码

class Solution:def canPartition(self, nums: List[int]) -> bool:n = len(nums)s = sum(nums)if s % 2 != 0:return Falsetarget = s // 2dp = [False] * (target + 1)dp[0] = Truefor i in range(1, target + 1):if nums[0] == i:dp[i] = Truefor i in range(1, n):# 0，1背包，反向遍历for j in range(target, nums[i] - 1, -1):dp[j] = dp[j] or dp[j - nums[i]]return dp[target]

---

32. 最长有效括号

题目描述

给定一个只包含 ‘(’ 和 ‘)’ 的字符串，找出最长有效（格式正确且连续）括号子串的长度。

解题思路

使用动态规划来解决。假设 dp[i] 表示以 i 结尾的最长有效括号的长度。状态转移方程根据当前字符和前一个字符的情况来判断。如果s[i]=‘(’，那么dp[i]一定是0， s[i] ='('的情况见代码中的注释。

Python代码

class Solution:#   ((()))#   012345def longestValidParentheses(self, s: str) -> int:n =len(s)dp = [0] * nres = 0for i in range(1, n):if s[i] == '(':continue# 当前是')', 前一个字符是'('if s[i - 1] == '(':if i == 1:dp[i] = 2else:dp[i] = dp[i-2] + 2# 当前是')', 前一个也是')'，那就需要判断s[i - 1 - dp[i-1]]是不是'('，是的话就能和当前的')'匹配上elif i - 1 - dp[i-1] >= 0 and s[i - 1 - dp[i-1]] == '(':dp[i] = dp[i-1] + 2if i - 2 - dp[i-1] >= 0:dp[i] += dp[i - 2 - dp[i-1]]res = max(res, dp[i])return res