动态规划是一种解决多阶段决策过程最优化问题的数学方法。通常需要保存决策路径的问题用回溯法，而只是求最优解的时候选择动态规划。
基本概念
定义：动态规划通过把原问题分解为相对简单的子问题，并保存子问题的解，避免重复计算，从而高效地求解复杂问题。它通常适用于具有最优子结构和子问题重叠性质的问题。
最优子结构：一个问题具有最优子结构意味着问题的最优解可以由子问题的最优解组合而成。例如，在求解最短路径问题中，从起点到终点的最短路径可以由从起点到中间点的最短路径和从中间点到终点的最短路径组成。
子问题重叠：子问题重叠是指在求解问题的过程中，会多次重复地求解相同的子问题。动态规划通过保存子问题的解，避免了重复计算这些子问题，从而提高了算法的效率。
解题步骤
确定问题的状态：状态是描述问题在不同阶段的特征。选择合适的状态表示是动态规划的关键。例如，在背包问题中，可以用背包的剩余容量和已选物品的集合来表示状态。
定义状态转移方程：状态转移方程描述了如何从一个状态转移到另一个状态。它通常是根据问题的最优子结构性质推导出来的。例如，在背包问题中，状态转移方程可以表示为：dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i])，其中dp[i][j]表示前i个物品放入容量为j的背包中的最大价值，w[i]和v[i]分别表示第i个物品的重量和价值。
确定初始状态和边界条件：初始状态是问题的最简单情况，边界条件是状态转移方程在特殊情况下的取值。例如，在背包问题中，初始状态可以是dp[0][j] = 0（没有物品时，背包价值为 0），边界条件可以是dp[i][0] = 0（背包容量为 0 时，背包价值为 0）。
计算最优解：根据状态转移方程和初始状态、边界条件，通过递推或递归的方式计算出问题的最优解。通常可以使用自底向上（递推）或自顶向下（记忆化搜索）的方法进行计算。
应用举例 打家劫舍 链接: https://leetcode.cn/problems/Gu0c2T/
一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响小偷偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组nums，请计算不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
示例 1：
输入：nums = [1,2,3,1]
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 class Solution : def rob (self, nums: List [int ] ) -> int : len_nums = len (nums) if len_nums == 0 : return 0 if len_nums == 1 : return nums[0 ] dp = [] dp.append(nums[0 ]) dp.append(max (nums[1 ], nums[0 ])) for idx in range (2 , len_nums, 1 ): dp[idx % 2 ] = max (dp[(idx - 1 ) % 2 ], dp[(idx - 2 ) % 2 ] + nums[idx]) return dp[(len_nums - 1 ) % 2 ]
打家劫舍2 链接：https://leetcode.cn/problems/PzWKhm/
环形房屋，即第一个房屋和最后一个房屋也不能同时被打劫。该问题可以看做是求以下两个子问题的最大值：
房屋0 到 房屋len - 2 (不打劫最后一间房屋)
房屋1 到 房屋len - 1 (不打劫第一间房屋)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 def helper (nums, start, end ): dp = [] dp.append(nums[start]) if start < end: dp.append(max (nums[start], nums[start + 1 ])) for i in range (start + 2 , end + 1 , 1 ): j = i - start dp[j % 2 ] = max (dp[(j - 1 ) % 2 ], dp[(j - 2 ) % 2 ] + nums[i]) return dp[(end - start) % 2 ] class Solution : def rob (self, nums: List [int ] ) -> int : len_nums = len (nums) if len_nums == 0 : return 0 if len_nums == 1 : return nums[0 ] return max (helper(nums, 0 , len (nums) - 2 ), helper(nums, 1 , len (nums) - 1 ))
粉刷房子 链接：https://leetcode.cn/problems/JEj789/description/
假如有一排房子，共 n 个，每个房子可以被粉刷成红色、蓝色或者绿色这三种颜色中的一种，你需要粉刷所有的房子并且使其相邻的两个房子颜色不能相同。
示例 2：
1 2 3 4 5 dp[0 ][i] = min (dp[1 ][i - 1 ], dp[2 ][i - 1 ]) + cost[i][0 ] dp[1 ][i] = min (dp[0 ][i - 1 ], dp[2 ][i - 1 ]) + cost[i][1 ] dp[2 ][i] = min (dp[1 ][i - 1 ], dp[0 ][i - 1 ]) + cost[i][2 ] result = min (dp[0 ][last], dp[1 ][last], dp[2 ][last])
1 2 3 dp[0 ][0 ] = cost[0 ][0 ] dp[1 ][0 ] = cost[0 ][1 ] dp[2 ][0 ] = cost[0 ][2 ]
1 2 3 4 5 6 7 8 9 10 11 12 13 def minCost (self, costs: List [List [int ]] ) -> int : len_costs = len (costs) last = len_costs - 1 if len_costs == 0 : return 0 dp = [[None for _ in range (len_costs)] for _ in range (3 )] for i in range (3 ): dp[i][0 ] = costs[0 ][i] for i in range (1 , len_costs): dp[0 ][i] = min (dp[1 ][i - 1 ], dp[2 ][i - 1 ]) + costs[i][0 ] dp[1 ][i] = min (dp[0 ][i - 1 ], dp[2 ][i - 1 ]) + costs[i][1 ] dp[2 ][i] = min (dp[1 ][i - 1 ], dp[0 ][i - 1 ]) + costs[i][2 ] return min (dp[0 ][last], dp[1 ][last], dp[2 ][last])
翻转字符 链接： https://leetcode.cn/problems/cyJERH/description/
如果一个由 ‘0’ 和 ‘1’ 组成的字符串，是以一些 ‘0’（可能没有 ‘0’）后面跟着一些 ‘1’（也可能没有 ‘1’）的形式组成的，那么该字符串是 单调递增 的。
示例 1：
输入：s = “00110”
示例 2：
输入：s = “010110”
示例 3：
输入：s = “00011000”
分析状态转移方程：
dp_f: 把当前字符翻转成”0”且符合单调递增条件的最小翻转次数
dp_g: 把当前字符翻转成”1”且符合单调递增条件的最小翻转次数
1 2 dp_f[i] = dp_f[i - 1 ] if s[i] == "0" else dp_f[i - 1 ] + 1 dp_g[i] = min (dp_f[i - 1 ], dp_g[i - 1 ]) if s[i] == "1" else min (dp_f[i - 1 ], dp_g[i - 1 ]) + 1
寻找初始值1 2 dp_f[0 ] = 0 if s[0 ] == "0" else 1 dp_g[0 ] = 0 if s[0 ] == "1" else 1
1 2 3 4 5 6 7 8 9 10 11 12 13 14 class Solution : def minFlipsMonoIncr (self, s: str ) -> int : len_s = len (s) if len_s <= 1 : return 0 f_cache = 0 if s[0 ] == "0" else 1 g_cache = 0 if s[0 ] == "1" else 1 dp_f = f_cache dp_g = g_cache for i in range (1 , len_s): dp_f = f_cache if s[i] == "0" else f_cache + 1 dp_g = min (g_cache, f_cache) if s[i] == "1" else min (g_cache, f_cache) + 1 f_cache, g_cache = dp_f, dp_g return min (dp_f, dp_g)
最长的斐波那契子序列的长度 如果序列 X_1, X_2, …, X_n 满足下列条件，就说它是 斐波那契式 的：
n >= 3
对于所有 i + 2 <= n，都有 X_i + X_{i+1} = X_{i+2}
给定一个严格递增的正整数数组形成序列 arr ，找到 arr 中最长的斐波那契式的子序列的长度。如果一个不存在，返回 0 。（回想一下，子序列是从原序列 arr 中派生出来的，它从 arr 中删掉任意数量的元素（也可以不删），而不改变其余元素的顺序。例如， [3, 5, 8] 是 [3, 4, 5, 6, 7, 8] 的一个子序列）
示例 1：
输入: arr = [1,2,3,4,5,6,7,8]
输出: 5
解释: 最长的斐波那契式子序列为 [1,2,3,5,8] 。
示例 2：
输入: arr = [1,3,7,11,12,14,18]
输出: 3
解释: 最长的斐波那契式子序列有 [1,11,12]、[3,11,14] 以及 [7,11,18] 。
提示：
3 <= arr.length <= 1000
1 <= arr[i] < arr[i + 1] <= 10^9
1 2 3 4 if 0 <= arr.find[arr[i] - arr[j]] < j: dp[i][j] = dp[j][k] + 1 else : dp[i][j] = 2
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 class Solution : def lenLongestFibSubseq (self, arr: List [int ] ) -> int : len_arr = len (arr) if len_arr <= 2 : return 0 max_len = 0 v_map = {v: i for i, v in enumerate (arr)} dp = [[0 ] * len_arr for _ in range (0 , len_arr)] dp[1 ][0 ] = 2 for i in range (1 , len_arr): for j in range (0 , i): d = arr[i] - arr[j] if d in v_map and 0 <= v_map[d] < j: dp[i][j] = dp[j][v_map[d]] + 1 else : dp[i][j] = 2 max_len = max (max_len, dp[i][j]) return 0 if max_len < 3 else max_len
最少回文分隔 链接：https://leetcode.cn/problems/omKAoA/
给定一个字符串 s，请将 s 分割成一些子串，使每个子串都是回文串。返回符合要求的最少分割次数
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 class Solution : def minCut (self, s: str ) -> int : len_s = len (s) if len_s < 2 : return 0 valid = [[False ] * len_s for _ in range (len_s)] for i in range (len_s): for j in range (0 , i + 1 ): if j == i: valid[i][j] = True else : valid[i][j] = (j + 1 >= i or valid[i - 1 ][j + 1 ]) and s[i] == s[j] dp = [0 ] * len_s for i in range (0 , len_s): if valid[i][0 ]: dp[i] = 0 else : dp[i] = i for j in range (1 , i + 1 ): if valid[i][j]: dp[i] = min (dp[i], dp[j - 1 ] + 1 ) return dp[len_s - 1 ]
最长公共子序列 链接: https://leetcode.cn/problems/qJnOS7/
给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。
技巧：多创建一个数组项来表示下标为-1的情况，即为空字符创
状态转移方程：
1 2 dp[i][j] = dp[i - 1 ][j - 1 ] + 1 if text1[i - 1 ] == text2[j - 1 ] dp[i][j] = max (dp[i - 1 ][j], dp[i][j - 1 ]) text1[i - 1 ] ！= text2[j - 1 ]
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 class Solution : def longestCommonSubsequence (self, text1: str , text2: str ) -> int : if not text1 or not text2: return 0 len_1 = len (text1) len_2 = len (text2) if len_1 == 1 : return 1 if text1[0 ] in text2 else 0 if len_2 == 1 : return 1 if text2[0 ] in text1 else 0 dp = [[0 ] * (len_2 + 1 ) for _ in range (len_1 + 1 )] dp[0 ][0 ] = 0 dp[0 ][1 ] = 0 dp[1 ][0 ] = 0 for i in range (1 , len_1 + 1 ): for j in range (1 , len_2 + 1 ): if text1[i - 1 ] == text2[j - 1 ]: dp[i][j] = dp[i - 1 ][j - 1 ] + 1 else : dp[i][j] = max (dp[i - 1 ][j], dp[i][j - 1 ]) return dp[len_1][len_2]
字符串交织 链接：https://leetcode.cn/problems/IY6buf/description/
给定三个字符串 s1、s2、s3，请判断 s3 能不能由 s1 和 s2 交织（交错） 组成。
s = s1 + s2 + ... + sn
t = t1 + t2 + ... + tm
|n - m| <= 1
交织 是 s1 + t1 + s2 + t2 + s3 + t3 + ... 或者 t1 + s1 + t2 + s2 + t3 + s3 + ...
提示：a + b 意味着字符串 a 和 b 连接。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 class Solution : def isInterleave (self, s1: str , s2: str , s3: str ) -> bool : len_s1 = len (s1) len_s2 = len (s2) len_s3 = len (s3) if len_s1 + len_s2 != len_s3: return False dp = [[0 ] * (len_s2 + 1 ) for _ in range (len_s1 + 1 )] for i in range (len_s1 + 1 ): dp[i][0 ] = True if s1[:i] == s3[:i] else False for i in range (len_s2 + 1 ): dp[0 ][i] = True if s2[:i] == s3[:i] else False for i in range (len_s1): for j in range (len_s2): if s1[i] == s3[i + j + 1 ] and s3[i + j + 1 ] != s2[j]: dp[i + 1 ][j + 1 ] = dp[i][j + 1 ] elif s2[j] == s3[i + j + 1 ] and s3[i + j + 1 ] != s1[i]: dp[i + 1 ][j + 1 ] = dp[i + 1 ][j] elif s1[i] == s2[j] == s3[i + j + 1 ]: dp[i + 1 ][j + 1 ] = dp[i][j + 1 ] or dp[i + 1 ][j] else : dp[i + 1 ][j + 1 ] = False return dp[len_s1][len_s2]
子序列的数目 链接： https://leetcode.cn/problems/21dk04/
给定一个字符串 s 和一个字符串 t ，计算在 s 的子序列中 t 出现的个数。
示例 1：
输入：s = "rabbbit", t = "rabbit"
输出：3
解释：
如下图所示, 有 3 种可以从 s 中得到 "rabbit" 的方案。
rabbbit
rabbbit
rabbbit
示例 2：
输入：s = "babgbag", t = "bag"
输出：5
解释：
如下图所示, 有 5 种可以从 s 中得到 "bag" 的方案。
babgbag
babgbag
babgbag
babgbag
babgbag
1 2 3 4 5 6 dp[0 ][*] = 0 dp[*][0 ] = 1 dp[i][j] = 0 if i < j dp[i][j] = 1 if i == j and s[:i] == t[:j] dp[i][j] = 0 if i == j and s[:i] == t[:j] dp[i][j] = dp[i - 1 ][j - 1 ] + dp[i - 1 ][j] if s[i - 1 ] == s[j - 1 ] else dp[i - 1 ][j]
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 class Solution : def numDistinct (self, s: str , t: str ) -> int : lenS = len (s) lenT = len (t) if not lenS: return 0 if not lenT: return 1 dp = [[None ] * (lenT + 1 ) for _ in range (lenS + 1 )] for i in range (lenT + 1 ): dp[0 ][i] = 0 for i in range (lenS + 1 ): dp[i][0 ] = 1 for i in range (1 , lenS + 1 ): for j in range (1 , lenT + 1 ): if j > i: dp[i][j] = 0 if i == j: dp[i][j] = 1 if s[:i] == t[:j] else 0 if j < i: if s[i - 1 ] == t[j - 1 ]: dp[i][j] = dp[i - 1 ][j - 1 ] + dp[i - 1 ][j] else : dp[i][j] = dp[i - 1 ][j] return dp[lenS][lenT]
微信
支付宝
