动态规划（动态规划模型的建立与求解）

动态规划（动态规划模型的建立与求解）

1. 斐波那契数列

斐波那契数 （通常用 F(n) 表示）形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是： F(0) = 0，F(1) = 1 F(n) = F(n - 1) + F(n - 2)，其中 n > 1 给定 n ，请计算 F(n) 。 示例 1： 输入：n = 2 输出：1 解释：F(2) = F(1) + F(0) = 1 + 0 = 1 示例 2： 输入：n = 3 输出：2 解释：F(3) = F(2) + F(1) = 1 + 1 = 2 示例 3： 输入：n = 4 输出：3 解释：F(4) = F(3) + F(2) = 2 + 1 = 3   提示： 0 <= n <= 30

题解：

class Solution: def fib(self, n: int) -> int: if n == 0: return 0 if n == 1: return 1 dp = [0] * (n + 1) # 定义 dp 数组 dp[0] = 0 # 初始化 dp[1] = 1 for i in range(2, n+1): dp[i] = dp[i - 1] + dp[i - 2] # 递推公式 return dp[n]

2. 爬楼梯

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？ 示例 1： 输入：n = 2 输出：2 解释：有两种方法可以爬到楼顶。 1. 1 阶 + 1 阶 2. 2 阶 示例 2： 输入：n = 3 输出：3 解释：有三种方法可以爬到楼顶。 1. 1 阶 + 1 阶 + 1 阶 2. 1 阶 + 2 阶 3. 2 阶 + 1 阶   提示： 1 <= n <= 45

爬楼梯实质上也可以看作一个斐波拉契数列：

class Solution: def climbStairs(self, n: int) -> int: dp = [0] * (n+1) dp[0] = 1 dp[1] = 1 for i in range(2, n+1): dp[i] = dp[i-1] + dp[i-2] return dp[n]

类似题目 剑指 Offer 10- II. 青蛙跳台阶问题：

class Solution: def numWays(self, n: int) -> int: if n == 0 or n == 1: return 1 dp = [0] * (n + 1) dp[0] = 1 # 0 个台阶有 1 种 方法 dp[1] = 1 # 1 个台阶有 1 种方法 for i in range(2, n + 1): dp[i] = dp[i - 1] + dp[i - 2] return dp[n] % 1000000007

3. 不同路径

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。 问总共有多少条不同的路径？ 示例 1： 输入：m = 3, n = 7 输出：28 示例 2： 输入：m = 3, n = 2 输出：3 解释： 从左上角开始，总共有 3 条路径可以到达右下角。 1. 向右 -> 向下 -> 向下 2. 向下 -> 向下 -> 向右 3. 向下 -> 向右 -> 向下 示例 3： 输入：m = 7, n = 3 输出：28 示例 4： 输入：m = 3, n = 3 输出：6   提示： 1 <= m, n <= 100 题目数据保证答案小于等于 2 * 109

题解一：

class Solution: def uniquePaths(self, m: int, n: int) -> int: dp = [[0 for i in range(n)] for j in range(m)] def diff_path(row, col): # 第一列的任意单元格，只有来自它上一个单元格过来的方法 for i in range(n): dp[0][i] = 1 # 第一行的任意单元格，只有来自它前一个单元格过来的一种方法 for j in range(m): dp[j][0] = 1 # 随意一个单元格有来自上或者左的两种路径，第一行、第一列已填充，不用继续填充 for i in range(1, row): for j in range(1, col): dp[i][j] = dp[i - 1][j] + dp[i][j - 1] # 返回最后一个单元格的位置 return dp[row - 1][col - 1] return diff_path(m, n)

题解二：（更容易理解）

class Solution: def uniquePaths(self, m: int, n: int) -> int: dp = [[0] * n for i in range(m)] for row in range(m): for col in range(n): # 第一个格子只有一种方法 if row == 0 and col == 0: dp[row][col] = 1 elif col == 0: # 第一行的任意单元格，只有来自它前一个单元格过来的一种方法 dp[row][col] = dp[row-1][col] elif row == 0: # 第一列的任意单元格，只有来自它上一个单元格过来的方法 dp[row][col] = dp[row][col - 1] else: # 其他情况（中间）：任意一个单元格有来自其左或上两个方向的机器人 dp[row][col] = dp[row - 1][col] + dp[row][col - 1] return dp[m - 1][n - 1]

4. 不同路径 II

示例 1： 输入：obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]] 输出：2 解释：3x3 网格的正中间有一个障碍物。 从左上角到右下角一共有 2 条不同的路径： 1. 向右 -> 向右 -> 向下 -> 向下 2. 向下 -> 向下 -> 向右 -> 向右 示例 2： 输入：obstacleGrid = [[0,1],[0,0]] 输出：1   提示： m == obstacleGrid.length n == obstacleGrid[i].length 1 <= m, n <= 100 obstacleGrid[i][j] 为 0 或 1

题解：

class Solution: def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int: row = len(obstacleGrid) col = len(obstacleGrid[0]) # 只有一个单元格，即一行一列时 if row == 1 and col == 1: if obstacleGrid[0][0] == 1: return 0 else: return 1 dp = [[0] * col for i in range(row)] for i in range(row): for j in range(col): # 遇到阻碍，就跳过当前循环 if obstacleGrid[i][j] == 1: continue if i == 0 and j == 0: dp[i][j] = 1 elif i == 0: dp[i][j] = dp[i][j - 1] elif j == 0: dp[i][j] = dp[i - 1][j] else: dp[i][j] = dp[i][j - 1] + dp[i - 1][j] return dp[row - 1][col - 1]

5. 最小路径和

给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。 说明：每次只能向下或者向右移动一步。 示例 1： 输入：grid = [[1,3,1],[1,5,1],[4,2,1]] 输出：7 解释：因为路径 1→3→1→1→1 的总和最小。 示例 2： 输入：grid = [[1,2,3],[4,5,6]] 输出：12   提示： m == grid.length n == grid[i].length 1 <= m, n <= 200 0 <= grid[i][j] <= 100

题解：

class Solution: def minPathSum(self, grid: List[List[int]]) -> int: m, n = len(grid), len(grid[0]) # 只有一个单元格时 if m == 1 and n == 1: return grid[0][0] dp = [[0] * n for i in range(m)] for i in range(m): for j in range(n): if i == 0: # 第一行，和 = 当前单元格数字 + 前一个单元格数字 dp[i][j] = dp[i][j - 1] + grid[i][j] elif j == 0: # 第一列，和 = 当前单元格数字 + 上一个单元格数字 dp[i][j] = dp[i - 1][j] + grid[i][j] else: # 中间单元格，和 = 当前单元格数字 + 上一个和前一个单元格中最小的数字 dp[i][j] = min(dp[i][j - 1], dp[i - 1][j]) + grid[i][j] return dp[m-1][n-1]

注意：dp[i][j - 1]、dp[i - 1][j] 代表的是状态转移，它包括前面走过的路径之和，而 grid[i][j] 代表的仅仅只是当前单元格一个数字，所以是：dp[i][j] = dp[i][j - 1] + grid[i][j]，而不是 dp[i][j] = grid[i][j - 1] + grid[i][j]

6. 最长递增子序列

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。 子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。 示例 1： 输入：nums = [10,9,2,5,3,7,101,18] 输出：4 解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。 示例 2： 输入：nums = [0,1,0,3,2,3] 输出：4 示例 3： 输入：nums = [7,7,7,7,7,7,7] 输出：1   提示： 1 <= nums.length <= 2500 -104 <= nums[i] <= 104

题解：

dp[i] 表示当前元素的递增子集个数

元素 1: 因为没有比它小的元素，所以递增子集数为 1 元素 7：递增子集有：1、 17 即 1 + dp[0] 元素 2：递增子集有：因为 7 比 2 大，所以只有 1、 12，即 1 + dp[0] 元素 5：递增子集有：1 、 15、 125，即 1 + dp[2] 如此类推就能推出 dp[i]

class Solution: def lengthOfLIS(self, nums: List[int]) -> int: n = len(nums) if n == 1: return 1 dp = [1] * n res = 1 for i in range(n): for j in range(i): # 当前元素与它之前所有的元素进行比较，若之前元素比当前元素大，则跳过不考虑，只需要考虑比它小的即可 if nums[i] > nums[j]: dp[i] = max(dp[j] + 1, dp[i]) res = max(res, dp[i]) return res

参考：【算法太难了】【23】最长递增子序列-动态规划

7. 最长公共子序列

给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。 一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。 例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。 两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。 示例 1： 输入：text1 = "abcde", text2 = "ace" 输出：3 解释：最长公共子序列是 "ace" ，它的长度为 3 。 示例 2： 输入：text1 = "abc", text2 = "abc" 输出：3 解释：最长公共子序列是 "abc" ，它的长度为 3 。 示例 3： 输入：text1 = "abc", text2 = "def" 输出：0 解释：两个字符串没有公共子序列，返回 0 。

题解：

对于两个字符串求子序列的问题，都是用两个指针i和j分别在两个字符串上移动，大概率是动态规划思路

class Solution: def longestCommonSubsequence(self, text1: str, text2: str) -> int: # dp 函数的定义：dp(s1, i, s2, j) 计算 s1[i..]和s2[j..]的最长公共子序列长度 dp = [[-1 for _ in text2] for _ in text1] def ways(s1, i, s2, j): # bad case，此时 s1 或 s2 相当于空串了 if len(s1) == i or len(s2) == j: return 0 # 备忘录，避免重复计算 if dp[i][j] != -1: return dp[i][j] # 比较两个字符串是否相等，若相等一定这个字符串一定在 lcs 中 if s1[i] == s2[j]: dp[i][j] = 1 + ways(s1, i+1, s2, j+1) else: # 不相等，则 s1[i] 、s2[j] 至少有一个不在 lcs 中 dp[i][j] = max( ways(s1, i+1, s2, j), # s1[i] 不在 lcs 中 ways(s1, i, s2, j+1), # s2[j] 不在 lcs 中 ways(s1, i+1, s2, j+1) # 都不在 lcs 中（这一步可省略，因为前面两步已经包含了） ) return dp[i][j] return ways(text1, 0, text2, 0)

8. 最长回文子序列

给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。 子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。   示例 1： 输入：s = "bbbab" 输出：4 解释：一个可能的最长回文子序列为 "bbbb" 。 示例 2： 输入：s = "cbbd" 输出：2 解释：一个可能的最长回文子序列为 "bb" 。   提示： 1 <= s.length <= 1000 s 仅由小写英文字母组成

题解：

用 dp[i][j 表示字符串 s 下标范围 [i, j] 内最长回文子序列的长度，假设字符串 s 的长度为 n，则只有当 0<=i<j<n 时，才会有 dp[i][j] > 0，否则有 dp[i][j]=0

class Solution: def longestPalindromeSubseq(self, s: str) -> int: n = len(s) dp = [[0] * n for _ in range(n)] # 倒序递归 for i in range(n-1, -1, -1): # bad case，若只有一个字符，最长回文子序列长度是 1，dp[i][j] = 1 (i == j) dp[i][i] = 1 for j in range(i+1, n): # 它俩一定在最长回文子序列中 if s[i] == s[j]: dp[i][j] = dp[i+1][j-1] + 2 else: # s[i+1..j] 和 s[i..j-1] 谁的回文子序列更长 dp[i][j] = max(dp[i+1][j], dp[i][j-1]) return dp[0][n-1]

参考：子序列问题通用思路|最长回文子序列

9. 最长回文子串

给你一个字符串 s，找到 s 中最长的回文子串。 示例 1： 输入：s = "babad" 输出："bab" 解释："aba" 同样是符合题意的答案。 示例 2： 输入：s = "cbbd" 输出："bb"   提示： 1 <= s.length <= 1000 s 仅由数字和英文字母组成

题解：

解题思路：中心拓展法，从当前字符向两端进行拓展（两个指针背向移动），每个位置都判断下，以该位置为中心的回文串最长为多少，遍历一遍，保留最长的那个

class Solution: def longestPalindrome(self, s: str) -> str: long_sub = "" for i in range(len(s)): odd = self.is_palindrom(s, i, i) # 回文串元素个数为奇数 even = self.is_palindrom(s, i, i + 1) # 回文串元素个数为偶数 long_sub = odd if len(odd) > len(long_sub) else long_sub long_sub = even if len(even) > len(long_sub) else long_sub return long_sub def is_palindrom(self, s, l, r): """不超出边界且扩散的两边的元素相等，返回回文子串""" while l >= 0 and r < len(s) and s[l] == s[r]: l -= 1 r += 1 return s[l + 1: r]

模拟：

s = 'babad' n = len(s) = 5 i = 0 奇数：l = 0, r = 0 ==> s[l] == s[r] ==> l = -1, r = 1 ===> s[0: 1] ==> long_sub = "b" 偶数: l = 0, r = 1 ==> s[l] != s[r] ===> s[0: 1] ==> long_sub = "b" i = 1 奇数：l = 1, r = 1 ==> s[l] == s[r] ==> l = 0, r = 2 ===> l = -1, r = 3 ===> s[0: 3] ==> long_sub = "bab" 偶数: l = 1, r = 2 ==> s[l] != s[r] ===> s[2: 2] ==> long_sub = "bab" ....

参考：【山鬼】左右指针——从中心往外扩散

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。