上海人才网官方网站,如何编写一套网站模板,wordpress公司,怎么做电商无货源模式《博主简介》 小伙伴们好#xff0c;我是阿旭。专注于人工智能AI、python、计算机视觉相关分享研究。 ✌更多学习资源#xff0c;可关注公-仲-hao:【阿旭算法与机器学习】#xff0c;共同学习交流~ #x1f44d;感谢小伙伴们点赞、关注#xff01; 《------往期经典推荐--… 《博主简介》 小伙伴们好我是阿旭。专注于人工智能AI、python、计算机视觉相关分享研究。 ✌更多学习资源可关注公-仲-hao:【阿旭算法与机器学习】共同学习交流~ 感谢小伙伴们点赞、关注 《------往期经典推荐------》
一、AI应用软件开发实战专栏【链接】二、机器学习实战专栏【链接】已更新31期欢迎关注持续更新中~~三、深度学习【Pytorch】专栏【链接】四、【Stable Diffusion绘画系列】专栏【链接】
《------正文------》
这篇文章是博主在学习动态规划系列算法过程中精心总结的42页学习笔记其中包含了动态规划的原理详解以及LeetCode中的动态规划题目汇总。
免费分享给需要的下伙伴。原版文档获取方式见文末。
目录
介绍
定义
应用场景
核心
动态规划特点三要素
通常的思考过程
状态转移方程一般过程
解题方法
DP数组注意事项
举例
1.斐波拉契数列
暴力递归时间复杂度2^n指数级
带备忘录的递归
DP数组的迭代解法
2.零钱兑换问题
暴力解法
带备忘录的递归
DP数组迭代解法
经典题目
*最长回文子串
*最长有效括号
*不同的子序列
*最长公共子序列
*最长公共子串
*最长上升子序列
**编辑距离
最长重复子数组
完全平方数
不同路径1
不同路径2
不同路径3回溯
零钱兑换1
零钱兑换2
最大正方形
最大矩形
最大子序和
三角形最小路径和
乘积最大子数组
打家劫舍
最小路径和
买卖股票问题
买卖股票的最佳时机2
使用最小花费爬楼梯
解码方法
赛车
播放列表的数量 介绍
定义
动态规划时一种运筹学方法是在多轮决策过程中的最优方法。
应用场景
动态规划问题的一般形式就是求最值。动态规划其实是运筹学的一种最优化方法只不过在计算机问题上应用比较多比如说让你求最长递增子序列呀最小编辑距离呀等等。
核心
求解动态规划的核心问题是穷举。因为要求最值肯定要把所有可行的答案穷举出来然后在其中找最值。
动态规划特点三要素
1.最优子结构原问题的最优解所包含的子问题的解也是最优的通过子问题的最值得到原问题的最值。
2.存在重叠子问题子问题间不独立这是动态规划区别于分治的最大不同如果暴力穷举的话效率会极其低下所以需要「备忘录」或者「DP table」来优化穷举过程避免不必要的计算
3.无后效性即后续的结果不会影响当前结果。
通常的思考过程
动态规划没有标准的解题方法但在宏观上有通用的方法论
下面的 k 表示多轮决策的第 k 轮
1.分阶段将原问题划分成几个子问题。一个子问题就是多轮决策的一个阶段它们可以是不满足独立性的。
2.找状态选择合适的状态变量 Sk。它需要具备描述多轮决策过程的演变更像是决策可能的结果。
3.做决策确定决策变量 uk。每一轮的决策就是每一轮可能的决策动作例如 D2 的可能的决策动作是 D2 - E2 和 D2 - E3。
4.状态转移方程。这个步骤是动态规划最重要的核心即 sk1 uk(sk) 。
5.定目标。写出代表多轮决策目标的指标函数 Vk,n。
6.寻找终止条件。
状态转移方程一般过程
状态转移方程一般思考过程明确「状态」 - 定义 dp 数组/函数的含义 - 明确「选择」- 明确 base case。方程本质是数学的递推式
解题方法
递归是一种自顶向下的求解方式DP数组是一种自底向上的求解方式。
1.递归寻找暴力解自顶向下求解
2.通过备忘录memo优化递归过程剔除重复计算消除一下重叠子问题
3.通过DP table 自底向上求解主要是需要明确DP数组的含义定义然后通过递推进行推导。
DP数组注意事项
数组的遍历方向 # 正向遍历 int[][] dp new int[m][n]; for (int i 0; i m; i) for (int j 0; j n; j) // 计算 dp[i][j] # 反向遍历 for (int i m - 1; i 0; i--) for (int j n - 1; j 0; j--) // 计算 dp[i][j] # 斜向遍历 for (int l 2; l n; l) for (int i 0; i n - l; i) int j l i - 1; // 计算 dp[i][j] DP数组的递推计算过程需要注意两点
1、遍历的过程中所需的状态必须是已经计算出来的。
2、遍历的终点必须是存储结果的那个位置
主要就是看 base case 和最终结果的存储位置。
如编辑距离问题正向遍历 回文子序列问题从左至右斜着遍历或从下向上从左到右遍历都可以 举例
1.斐波拉契数列
暴力递归时间复杂度2^n指数级 def fib(n): if n 2: return 1 return fib(n-1) fib(n-2) 带备忘录的递归 def fib(n): def helper(n): if n 2: return 1 if n in memo: return memo[n] memo[n] fib(n-1) fib(n-2) return memo[n] memo {} # 记录已经计算过的值防止重复计算 return helper(n)
DP数组的迭代解法
上述递归过程是自顶向下求解的dp数组则是自底向上求解的。 def fib(n): dp [0 for _ in range(n1)] dp[1] dp[2] 1 for i in range(3, n 1): dp[i] dp[i-1] dp[i-2] return dp[n]
根据斐波那契数列的状态转移方程当前状态只和之前的两个状态有关其实并不需要那么长的一个 DP table 来存储所有的状态只要想办法存储之前的两个状态就行了。所以可以进一步优化把空间复杂度降为 O(1) def fib(n): if n 2: return 1 prev 1 curr 1 for i in range(3,n1): prev, curr curr, prev curr return curr
2.零钱兑换问题 题目给你 k 种面值的硬币面值分别为 c1, c2 ... ck每种硬币的数量无限再给一个总金额 amount问你最少需要几枚硬币凑出这个金额如果不可能凑出算法返回 -1 。
状态转移方程 # 伪码框架 def coinChange(coins: List[int], amount: int): # 定义要凑出金额 n至少要 dp(n) 个硬币 def dp(n): # 做选择选择需要硬币最少的那个结果 for coin in coins: res min(res, 1 dp(n - coin)) return res # 我们要求的问题是 dp(amount) return dp(amount)
实际代码
暴力解法 def coinChange(coins, amount): def dp(n): # 函数定义为目标金额为n时所需的最少硬币数量 # base case # 目标金额为 0 时所需硬币数量为 0当目标金额小于 0 时无解返回 -1 if n 0: return 0 if n 0: return -1 # 求最小值所以初始化结果为正无穷 res float(inf) for coin in coins: subpro dp(n-coin) if subpro -1: # 子问题无解跳过 continue res min(res, 1 subpro) return res if res ! float(inf) else -1 return dp(amount)
带备忘录的递归 def coinChange(coins, amount): def dp(n): # 函数定义为目标金额为n时所需的最少硬币数量 # base case # 目标金额为 0 时所需硬币数量为 0当目标金额小于 0 时无解返回 -1 if n 0: return 0 if n 0: return -1 if n in memo: return memo[n] # 求最小值所以初始化结果为正无穷 res float(inf) for coin in coins: subpro dp(n-coin) if subpro -1: # 子问题无解跳过 continue res min(res, 1 subpro) memo[n] res if res ! float(inf) else -1 return memo[n] memo {} return dp(amount)
DP数组迭代解法
dp[i] x 表示当目标金额为 i 时至少需要 x 枚硬币。 def coinChange(coins, amount): # 数组大小为 amount 1初始值也为 amount 1 # 因为总的零钱个数不会超过amount,所以初始化amount 1即可 dp [amount 1 for _ in (amount 1)] dp[0] 0 for i in range(len(dp)): # 内层 for循环求解的是所有子问题 1 的最小值 for coin in coins: # 子问题无解跳过 if i - coin 0: continue dp[i] min(dp[i],1dp[i-coin]) if dp[amount] amount 1: return -1 else: return dp[amount]
注dp 数组初始化为 amount 1 呢因为凑成 amount 金额的硬币数最多只可能等于 amount全用 1 元面值的硬币所以初始化为 amount 1 就相当于初始化为正无穷便于后续取最小值。 这个题目相当于是组合问题每个硬币可以用多次一共有多少种组合。
说明前k个硬币凑齐金额i的组合数等于前k-1个硬币凑齐金额i的组合数加上在原来i-k的基础上使用硬币的组合数。说的更加直白一点那就是用前k的硬币凑齐金额i要分为两种情况开率一种是没有用前k-1个硬币就凑齐了一种是前面已经凑到了i-k现在就差第k个硬币了。
DP[i] DP[i] DP[i-k]:
式子右边的DP[i]表示不使用第K个金币的和为i的组合, DP[i-k]表示使用金币k的和为i的组合数。 第 39 题问的是所有的组合列表需要知道每一个组合是什么应该使用 回溯算法 求解并且存储每一个组合
第 518 题问的是组合有多少种而不是问具体的解。应该使用 动态规划 求解 class Solution: def change(self, amount: int, coins: List[int]) - int: # 子问题:对于硬币从0到k我们必须使用第k个硬币的时候当前金额的组合数 # 状态数组DP[i]表示对于第k个硬币能凑的组合数 # 转移方程DP[i] DP[i] DP[i-k] dp [0] * (amount 1) dp[0] 1 for coin in coins: for x in range(1, amount 1): if x coin: continue # coin不能大于amount dp[x] dp[x - coin] return dp[amount] 这个题实际上是排列问题因为顺序不同的话视为不同的组合。 class Solution: def combinationSum4(self, nums: List[int], target: int) - int: dp [0] * (target 1) dp[0] 1 for x in range(1, target 1): for num in nums: if x num:continue dp[x] dp[x - num] return dp[target] 参考
https://leetcode-cn.com/problems/coin-change-2/solution/ling-qian-dui-huan-iihe-pa-lou-ti-wen-ti-dao-di-yo/
https://leetcode-cn.com/problems/coin-change-2/solution/ling-qian-dui-huan-ii-by-leetcode/
总结
518零钱兑换2是一个组合问题DP先遍历零钱列表再遍历amount金额数 def change(coins,amount): # 求的是组合数 dp [0 for _ in range(amount1)] dp[0] 1 for coin in coins: # 枚举硬币 for i in range(amount 1): # 枚举金额 if i coin: continue #coin不能大于amount dp[i] dp[i] dp[i - coin] return dp[amount] 377组合个数是一个排列问题 DP先遍历amount金额数再遍历零钱列表。 def change(coins,amount): # 求的是排列数 dp [0 for _ in range(amount1)] dp[0] 1 for i in range(amount 1): # 枚举金额 for coin in coins: #枚举硬币 if i coin: continue #coin不能大于amount dp[i] dp[i] dp[i - coin] return dp[amount]
举例
在LeetCode上有两道题目非常类似分别是
70.爬楼梯 --排列问题
518. 零钱兑换 II -- 组合问题
如果我们把每次可走步数/零钱面额限制为[1,2], 把楼梯高度/总金额限制为3. 那么这两道题目就可以抽象成给定[1,2], 求组合成3的组合数和排列数。
爬台阶问题通用模板 def climbStairs(n): # 爬台阶问题通用模板 dp [0 for _ in range(n 1)] dp[0] 1 steps [1,2,4,5] for i in range(n1): for j in range(len(steps)): if i steps[j]: continue # 台阶少于跨越的步数 dp[i] dp[i] dp[i-steps[j]] return dp[n] 经典题目
*最长回文子串 # 动态规划 # 用 P(i,j)P(i,j) 表示字符串 s的第 i 到 j 个字母组成的串下文表示成 s[i:j]是否为回文串 class Solution: def longestPalindrome(self, s: str) - str: n len(s) dp [[False] * n for _ in range(n)] ans # 枚举子串的长度 l1 for l in range(n): # 枚举子串的起始位置 i这样可以通过 jil 得到子串的结束位置 for i in range(n-l): j i l if l 0: dp[i][j] True elif l 1: dp[i][j] (s[i] s[j]) else: dp[i][j] (dp[i 1][j - 1] and s[i] s[j]) if dp[i][j] and l 1 len(ans): ans s[i:j1] return ans # 中心扩展法 class Solution: def expandAroundCenter(self, s, left, right): while left 0 and right len(s) and s[left] s[right]: left - 1 right 1 return left 1, right - 1 def longestPalindrome(self, s: str) - str: # 中心扩展法每个字符从中心往两边扩展分奇偶 start, end 0, 0 for i in range(len(s)): left1, right1 self.expandAroundCenter(s, i, i) # 以当前字符为中心 left2, right2 self.expandAroundCenter(s, i, i 1) # 以当前字符与后面一个字符为中心 if right1 - left1 end - start: start, end left1, right1 if right2 - left2 end - start: start, end left2, right2 return s[start: end 1] *最长有效括号 法一动态规划 class Solution: def longestValidParentheses(self, s: str) - int: # 动态规划 # dp[i] 表示以i结尾的最长有效括号长度‘’对应的一定是0 n len(s) if n 0: return 0 dp [0] * n for i in range(1,n): # i- dp[i-1] -1是与当前)对称的位置 # dp[i-dp[i-1]-2] 表示与当前)对称的位置前面的有效括号长度需加上 if s[i]) and i - dp[i-1] - 10 and s[i - dp[i-1] - 1] (: dp[i] dp[i-1] dp[i-dp[i-1]-2] 2 return max(dp) 法二栈 class Solution: def longestValidParentheses(self, s: str) - int: # 栈来实现 stack [-1] length 0 max_length 0 for i in range(len(s)): if s[i] (: stack.append(i) else: stack.pop() if not stack: # 栈为空则添加当前右括号的索引入栈为分割标识 stack.append(i) else: length i - stack[-1] max_length max(max_length, length) return max_length *不同的子序列 class Solution: def numDistinct(self, s: str, t: str) - int: # S中T出现的个数 # dp[i][j]表示t的前i个字符串可以由s的前j个字符串组成多少个 n len(s) # 列 m len(t) # 行 dp [[0] * (n1) for _ in range(m1)] for j in range(n1): dp[0][j] 1 for i in range(1,m 1): for j in range(1, n 1): if t[i-1] s[j-1]: # 对应于两种情况s选择当前字母和不选择当前字母 # s选择当前字母dp[i-1][j-1] # s不选择当前字母 dp[i][j-1] dp[i][j] dp[i-1][j-1] dp[i][j-1] else: dp[i][j] dp[i][j-1] return dp[-1][-1] *最长公共子序列 参考https://leetcode-cn.com/problems/longest-common-subsequence/solution/dong-tai-gui-hua-zhi-zui-chang-gong-gong-zi-xu-lie/ # 动态规划 class Solution: def longestCommonSubsequence(self, text1: str, text2: str) - int: m len(text1) n len(text2) dp [[0] * (n 1) for _ in range(m 1)] for i in range(1, m1): for j in range(1, n1): if text1[i-1] text2[j-1]: dp[i][j] dp[i-1][j-1] 1 else: dp[i][j] max(dp[i][j-1],dp[i-1][j]) return dp[-1][-1] # 递归 class Solution: def longestCommonSubsequence(self, text1: str, text2: str) - int: # 递归 memo {} #备忘录 def dp(i, j): if i -1 or j -1: return 0 if (i,j) in memo: return memo[(i,j)] if text1[i] text2[j]: memo[(i,j)] dp(i-1, j-1) 1 else: memo[(i,j)] max(dp(i-1, j), dp(i,j-1)) return memo[(i,j)] return dp(len(text1)-1,len(text2)-1) *最长公共子串
注意与子序列不相同的是子串是连续的子序列可以是不连续的。 def LCS(s1,s2): #dp[i][j]表示以s1的i及s2的j结尾的最长公共子串长度 #如果s1[i-1] s2[j-1] 则dp[i][j] 0 m len(s1) n len(s2) dp [[0] *(n1) for _ in range(m 1)] maxLen 0 end 0 for i in range(1,m1): for j in range(1,n1): if s1[i-1] s2[j-1]: dp[i][j] dp[i-1][j-1] 1 else: dp[i][j] 0 if dp[i][j] maxLen: maxLen dp[i][j] end j-1 if maxLen 0: return else: return s2[end - maxLen 1:end 1] *最长上升子序列 class Solution: def lengthOfLIS(self, nums: List[int]) - int: if not nums: return 0 # dp[i]表示以第i个元素结尾的最长递增子序列长度 n len(nums) dp [1 for _ in range(n)] for i in range(n): for j in range(i): if nums[i] nums[j]: dp[i] max(dp[i],dp[j] 1) return max(dp) **编辑距离 class Solution: def minDistance(self, word1: str, word2: str) - int: # DP递推方程 # 存储 s1[0..i] 和 s2[0..j] 的最小编辑距离 m len(word1) n len(word2) dp [[0]*(n1) for i in range(m1)] for i in range(m1): dp[i][0] i for j in range(n1): dp[0][j] j for i in range(1, m1): for j in range(1,n1): if word1[i-1] word2[j-1]: dp[i][j] dp[i-1][j-1] else: dp[i][j] min(dp[i-1][j]1, dp[i][j-1]1, dp[i-1][j-1]1) return dp[m][n] # 递归写法 class Solution: def minDistance(self, word1: str, word2: str) - int: def dp(i,j): if i -1: return j 1 if j -1: return i 1 if (i,j) in memo: return memo[(i,j)] if word1[i] word2[j]: memo[(i,j)] dp(i-1,j-1) else: memo[(i,j)] min(dp(i-1,j) 1, dp(i,j-1) 1, dp(i-1,j-1) 1) return memo[(i,j)] memo {} res dp(len(word1)-1,len(word2)-1) return res 最长重复子数组 class Solution: def findLength(self, A: List[int], B: List[int]) - int: # p[i][j] 表示 A[i:] 和 B[j:] 的最长公共前缀那么答案即为所有 dp[i][j] 中的最大值。 # 如果 A[i] B[j]那么 dp[i][j] dp[i 1][j 1] 1否则 dp[i][j] 0。 # 考虑到这里 dp[i][j] 的值从 dp[i 1][j 1] 转移得到所以我们需要倒过来首先计算 dp[len(A) - 1][len(B) - 1]最后计算 dp[0][0] n, m len(A), len(B) dp [[0] * (m 1) for _ in range(n 1)] ans 0 for i in range(n - 1, -1, -1): for j in range(m - 1, -1, -1): dp[i][j] dp[i 1][j 1] 1 if A[i] B[j] else 0 ans max(ans, dp[i][j]) return ans 完全平方数 class Solution: def numSquares(self, n: int) - int: dp [0] * (n 1) for i in range(1, n 1): dp[i] i #最坏的情况就是全是1 j 1 while i - j*j 0: dp[i] min(dp[i], dp[i - j * j] 1) j 1 return dp[n] 不同路径1 class Solution: def uniquePaths(self, m: int, n: int) - int: dp [[0 for i in range(n)] for _ in range(m)] for i in range(m): dp[i][0] 1 for j in range(n): dp[0][j] 1 for i in range(1,m): for j in range(1,n): dp[i][j] dp[i-1][j] dp[i][j-1] return dp[-1][-1]
不同路径2 class Solution: def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) - int: m len(obstacleGrid) n len(obstacleGrid[0]) zero_loc {(i,j) for i in range(m) for j in range(n) if obstacleGrid[i][j] 1} dp [[0] * n for i in range(m)] for i in range(m): # 初始化第一列只要碰到一个1那么后边都无法走到 if obstacleGrid[i][0] 1: break dp[i][0] 1 for j in range(n): #初始化第一行只要碰到一个1那么后边都无法走到 if obstacleGrid[0][j] 1: break dp[0][j] 1 for i in range(1,m): for j in range(1,n): if (i,j) in zero_loc: dp[i][j] 0 else: dp[i][j] dp[i-1][j] dp[i][j-1] return dp[-1][-1] class Solution: def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) - int: m len(obstacleGrid) n len(obstacleGrid[0]) if obstacleGrid[0][0] 1 or obstacleGrid[-1][-1] 1: return 0 dp [[0] * n for _ in range(m)] for i in range(m): if obstacleGrid[i][0] 0: dp[i][0] 1 else: break for j in range(n): if obstacleGrid[0][j] 0: dp[0][j] 1 else: break for i in range(1,m): for j in range(1,n): if obstacleGrid[i][j] 1: dp[i][j] 0 continue dp[i][j] dp[i-1][j] dp[i][j-1] return dp[-1][-1] 不同路径3回溯 class Solution: def uniquePathsIII(self, grid: List[List[int]]) - int: # 注意每一个无障碍的格子都需要通过一次 start_x 0 start_y 0 steps 1 m len(grid) n len(grid[0]) # 遍历获取起始位置和统计总步数 for i in range(m): for j in range(n): if grid[i][j] 1: start_x i start_y j continue if grid[i][j] 0: steps 1 def DFS(x,y,cur_step, grid): # 排除越界的情况和遇到障碍的情况 if x 0 or x m or y 0 or y n or grid[x][y] -1: return 0 if grid[x][y] 2: # 走到2的位置且步数为0表示经过了所有的无障碍格子是一种方案 return 1 if cur_step 0 else 0 grid[x][y] -1 # 将已经走过的标记为障碍 res DFS(x - 1, y, cur_step - 1, grid) DFS(x 1, y, cur_step - 1, grid) \ DFS(x, y - 1, cur_step - 1, grid) \ DFS(x, y 1, cur_step - 1, grid) # 回溯 grid[x][y] 0 return res return DFS(start_x,start_y,steps,grid) 零钱兑换1 class Solution: def coinChange(self, coins: List[int], amount: int) - int: #dp[i] x 表示金额i最少需要x个金币 dp [amount 1 for i in range(amount 1)] dp[0] 0 for i in range(amount1): for coin in coins: if i - coin 0: continue dp[i] min(dp[i],dp[i-coin] 1) if dp[amount] amount 1: return -1 else: return dp[amount] 零钱兑换2 class Solution: def change(self, amount: int, coins: List[int]) - int: # 子问题:对于硬币从0到k我们必须使用第k个硬币的时候当前金额的组合数 # 状态数组DP[i]表示对于第k个硬币能凑的组合数 # 转移方程DP[i] DP[i] DP[i-k] dp [0] * (amount 1) dp[0] 1 for coin in coins: for x in range(coin, amount 1): dp[x] dp[x - coin] return dp[amount]
最大正方形 class Solution: def maximalSquare(self, matrix: List[List[str]]) - int: # 用 dp(i, j) 表示以 (i, j)为右下角且只包含 1的正方形的边长最大值 if len(matrix) 0 or len(matrix[0]) 0: return 0 maxSide 0 rows, columns len(matrix), len(matrix[0]) dp [[0] * columns for _ in range(rows)] for i in range(rows): for j in range(columns): if matrix[i][j] 1: if i 0 or j 0: dp[i][j] 1 else: dp[i][j] min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) 1 maxSide max(maxSide, dp[i][j]) maxSquare maxSide * maxSide return maxSquare 最大矩形 class Solution: def maximalRectangle(self, matrix: List[List[str]]) - int: #时间复杂度 : O(NM)。每次对于N的迭代我们会对M迭代常数次 if not matrix: return 0 m len(matrix) n len(matrix[0]) left [0] * n # initialize left as the leftmost boundary possible right [n] * n # initialize right as the rightmost boundary possible height [0] * n maxarea 0 for i in range(m): cur_left, cur_right 0, n # update height for j in range(n): if matrix[i][j] 1: height[j] 1 else: height[j] 0 # update left for j in range(n): if matrix[i][j] 1: left[j] max(left[j], cur_left) else: left[j] 0 cur_left j 1 # update right for j in range(n-1, -1, -1): if matrix[i][j] 1: right[j] min(right[j], cur_right) else: right[j] n cur_right j # update the area for j in range(n): maxarea max(maxarea, height[j] * (right[j] - left[j])) return maxarea 最大子序和 class Solution: def maxSubArray(self, nums: List[int]) - int: # dp[i] 表示以小标i为结尾的最大连续子序列的和dp[j] max(nums[j],dp[j-1] nums[j]) if len(nums) 0: return 0 if len(nums) 1: return nums[0] n len(nums) dp [float(-inf)] * n dp[0] nums[0] for j in range(1,n): dp[j] max(nums[j],dp[j-1] nums[j]) return max(dp)
三角形最小路径和 #法一 class Solution: def minimumTotal(self, triangle: List[List[int]]) - int: n len(triangle) f [[0] * n for _ in range(n)] f[0][0] triangle[0][0] for i in range(1, n): f[i][0] f[i - 1][0] triangle[i][0] for j in range(1, i): f[i][j] min(f[i - 1][j - 1], f[i - 1][j]) triangle[i][j] f[i][i] f[i - 1][i - 1] triangle[i][i] return min(f[n - 1]) #法二 class Solution: def minimumTotal(self, triangle: List[List[int]]) - int: n len(triangle) f [0] * n f[0] triangle[0][0] for i in range(1, n): f[i] f[i - 1] triangle[i][i] for j in range(i - 1, 0, -1): f[j] min(f[j - 1], f[j]) triangle[i][j] f[0] triangle[i][0] return min(f) 乘积最大子数组 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 n0: return 0 if n1: 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不确定因此需要通过遍历【0k-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]表示走剩余距离需要要使用的最少命令数加上已经使用的k1 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-j1) # 如果不是那么就是选择之前的一首歌之前最近的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] 关于本篇文章大家有任何建议或意见欢迎在评论区留言交流 觉得不错的小伙伴感谢点赞、关注加收藏哦 欢迎关注下方GZH阿旭算法与机器学习发送【动态规划】即可获取原版文档。欢迎小伙伴共同学习交流~
