升阳广州做网站公司,企业网站营销实现方式,书签制作 小学生的手工书签,装wordpress目录 一、基础理论
二、例题
1. 青蛙跳台阶
2. 解密数字
3. 最长不含重复字符的子字符串
4. 连续子数组的最大和
5. 最长递增子序列
6. 最长回文字符串
7. 机器人路径条数
8. 礼物的最大价值 一、基础理论
动态规划其实是一种空间换时间的基于历史数据的递推算法甚至有时连空间也可以节省。动态规划算法需要 3 个步骤。第一步决定用于记录历史计算结果的数据结构例如 dp[]第二步构建递推公式例如 dp[n]dp[n-1]dp[n-2]第三步设定初始值和递推顺序例如 dp[0]0, dp[1]1。
二、例题
1. 青蛙跳台阶
一只青蛙一次可以跳上 1 级台阶也可以跳上 2 级。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。
示例
输入3
输出3
本题首先使用 dp[i] 数据结构存储中间结算结果表示 i 级台阶的跳法数量由于要想跳到第 i 级台阶只能从第 i-1 级或者 i-2级台阶跳过来所以递推公式为 dp[i] dp[i-1] dp[i-2]由于想要跳到第 1 级台阶只有一种跳法要跳到第 2 级台阶有两种跳法所以初始值 dp[1]1, dp[2]2。
def jumpFloor(n):if (n 2):return ndp [0]*(n1) # 创建一个数组来保存历史数据多补了一个用不到的0位dp[1] 1 # 给出初始值dp[2] 2for i in range(3, n1): # 通过关系式来计算dp[n]dp[i] dp[i-1] dp[i-2]return dp[n]
该问题还可以进一步扩展为一只青蛙一次可跳上 1 级台阶也可以跳上 2 级 … 它也可以跳上 n 级。求该青蛙跳上一个n级的台阶n 为正整数总共有多少种跳法。
扩展问题无法用动态规划来解需要通过分析得到公式具体为
f(n) f(n-1) f(n-2) f(n-3) … f(1) f(n-1) f(n-2) f(n-3) … f(1) f(n) 2*f(n-1) n1
2. 解密数字
现有一串神秘的密文 ciphertext经调查密文的特点和规则如下
密文由非负整数组成数字 0-25 分别对应字母 a-z
请根据上述规则将密文 ciphertext 解密为字母并返回共有多少种解密结果。
示例:
输入: ciphertext 216612
输出: 6
解释: 216612 解密后有 6 种不同的形式分别是 cbggbcvggbcvggmcbggmcqggbc 和 cqggm
本题首先使用 dp[i] 表示长度为 i 的字符串的解法然后分析递推公式。如果第 i-1 数字为 0那 dp[i] dp[i-1]如果第 i-1 数字为 1那 dp[i] dp[i-1] dp[i-2]如果第 i-1 数字为 2且第 i 数字小于 6那 dp[i] dp[i-1] dp[i-2]如果第 i-1 数字大于 2那 dp[i] dp[i-1]。所以只需要 i-1 和 i 数字组成的数字大于等于 10 小于等于 25则 dp[i] dp[i-1] dp[i-2]否则 dp[i] dp[i-1]。需要注意在使用 dp 时我们在前面补一个用不到的 0这样做的目的是让索引 i 与实际长度匹配但是当需要访问 s 时需要注意 dp[i] 与 s[i-1] 对应。一定要理清楚 dp 与 s 的索引之间的关系否则很容易搞混了。
def translateNum(num):s str(num)dp [1] * (len(s)1) # 定义状态列表在0位置添加了一个1以便于递推公式的进行以及索引与实际长度匹配dp[1] 1 # 长度1时的解法for i in range(2, len(s)1): # 长度2到长度n的解法if int(s[i-2:i]) 9 and int(s[i-2:i]) 26: # dp[i]对应s[i-1]索引dp[i] dp[i-1] dp[i-2]else:dp[i] dp[i-1]return dp[-1]
3. 最长不含重复字符的子字符串
请从字符串中找出一个最长的不包含重复字符的子字符串计算该最长子字符串的长度。
示例 :
输入: abcabcbb
输出: 3 解释: 因为无重复字符的最长子串是 abc所以其长度为 3。
该问题首先使用 dp[i] 表示以 s[i] 为结点的最长不包含重复字符的字符串长度最终结果就是 dp 中的最大值。那递推公式很容易想到如果 s[i] 不存在于以 s[i-1] 为结点的最长不包含重复字符的字符串中那么 dp[i] dp[i-1] 1如果s[i] 存在于以 s[i-1] 为结点的最长不包含重复字符的字符串中且重复字符所在索引是 j那么 dp[i] i - j。此时引出一个问题如何获取这个字符串如何判断一个字符是否存在于这个字符串中以及如何获取重复字符的索引这个还是非常困难的。所以这里采用另外一种办法可以使用字典数据结构把所有的字符和索引均存储起来键是字符值是索引当字符存在重复时会被覆盖所以通过这个字典可以获取 s[j] 左侧是否存在重复字符如果存在可以获得最近的索引如果不存在可以使用默认值 -1 表示那么此时就可以通过 i-j 与 dp[i-1] 1 的大小比较以判断是否存在重复字符了但这种办法会增加内存使用量。这里初始值 dp[0] 1。
def lengthOfLongestSubstring(s): # 本函数有很多优化点但为了便于理解这里没有优化if not s: return 0 # 如果为空则返回 0 || 可优化掉dic {} # 定义哈希表用于获取最近相同字符的索引dic[s[0]] 0 # 初始化第一个字符对应的哈希表 || 可优化掉直接放进循环里dp [1] * len(s) # 初始化第一个字符对应的 dp || 可优化掉直接使用一个变量值记录res 1 # 初始化第一个字符的 res 结果for i in range(1, len(s)): # 从第二个字符开始处理j dic.get(s[i], -1) # 获取 s[i] 左侧最近相同元素的索引 jif dp[i-1] 1 i - j: # 如果 i-j 大于 dp[i-1]1 说明在 s[j] 并不存在于以 s[j-1] 为结点的最长无重复字符串中 || 可优化为min()函数dp[i] dp[i-1] 1else: # 反之dp[i] i - jdic[s[i]] i # 哈希表记录每个字符这会造成内存使用量偏高res max(res, dp[i])return res
针对本问题这里还有一个思路即实时维护一个集合当向右遍历字符串时使得集合中的元素使用对应着当前的最长无重复字符串。那此时就需要一个左指针 left 和一个右指针 i以及需要实时维护的集合 lookup。i 需要向右遍历所以 i 对应一个 for 循环。每遍历一个 i 值需要首先删除集合 lookup 中与 s[i] 重复的字符左侧的所有字符这里使用了一个很巧妙的办法即从 left 开始一直删除直至不存在重复。最后需要将当前字符 s[i] 放入集合中以完成针对 i 的遍历。此方案在空间消耗上要优于方案1。
def lengthOfLongestSubstring(s):if not s:return 0left 0 # 左指针lookup set() # 字典max_len 0cur_len 0for i in range(len(s)): # i是右指针每遍历一个ilookup都是由left到i的元素组成的字典cur_len 1while s[i] in lookup: # 每遍历一个i删除lookup中的重复元素并同步修改leftlookup.remove(s[left])left 1cur_len - 1 # 附带着同步修改当前i对应字符串的长度if cur_len max_len:max_len cur_lenlookup.add(s[i])return max_len
4. 连续子数组的最大和
输入一个长度为 n 的整型数组 array数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。
示例
输入[1,-2,3,10,-4,7,2,-5]
输出18
该问题取 dp[i] 作为以 s[i] 为结尾的连续子数组的最大和那 max(dp) 为最终结果。递推公式为 if dp[i-1]0: dp[i]dp[i-1]s[i] else: dp[i]s[i]。
def maxSubArray(nums):dp [nums[0]] * len(nums)for i in range(1, len(nums)):if dp[i-1] 0:dp[i] dp[i-1] nums[i]else:dp[i] nums[i]return max(dp)
如果不仅想要获取最大和还需要获取最大和所对应的字符串那就需要增加几个变量实时记录当前 dp[i] 所对应的字符串这里其实属于滑动窗口问题了滑动窗口的右边界很容易界定就是遍历的参数左边界不太好想清楚其实左边界只有在 dp[i-1] 小于 0 的时候才会更新且更新为 i想明白了这一点那就好编程了。
def maxSubArray(nums):dp [nums[0]] * len(nums)max_value nums[0]beign 0end 0max_beign 0max_end 0for i in range(1, len(nums)):if dp[i-1] 0:dp[i] dp[i-1] nums[i]else:dp[i] nums[i]beign i # 这个是最关键的点需要想清楚end iif dp[i] max_value:max_value dp[i]max_beign beignmax_end endreturn (max_value, nums[max_beign:max_end1])
5. 最长递增子序列
给你一个整数数组 nums 找到其中最长严格递增子序列的长度。子序列是由数组派生而来的序列删除或不删除数组中的元素而不改变其余元素的顺序。例如[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
示例
输入nums [10,9,2,5,3,7,101,18]
输出4 解释最长递增子序列是 [2,3,7,101]因此长度为 4 。
该问题选用 dp 作为中间数据存储结构以 dp[i] 表示以 s[i] 为结尾的最大递增子序列长度。接下来是递推公式首先想到的是与 dp[i-1] 之间的关系但是这次的子序列是允许跳跃的所以不一定只是与 dp[i-1] 之间有关系所以仔细想清楚后发现 dp[i] 其实与 dp[0]...dp[i-1] 都有关系需要找出来的是在 s[i]s[index] 前提下找到 max(dp[index]...)。 def lengthOfLIS(nums):dp [1]*len(nums)for i in range(len(nums)):for j in range(i):if nums[i] nums[j]:dp[i] max(dp[i], dp[j]1)return max(dp) 如果想要同步获取这个子序列那需要定义一个变量 result 保存所有的最长递增子序列reslut[i] 存储的是以 s[i] 为结尾的最长递增子序列。然后在更新 dp 的时候同步更新 result。这里需要特别注意的是 [[]]*len(nums) 的方式属于浅拷贝更新任何一个 [] 都会同步影响其它 []。在做 List 的整体赋值时一定注意好是需要赋值、浅拷贝还是深拷贝。深拷贝可以使用 copy 包或者 [:] 运算符。 import copydef lengthOfLIS(nums):dp [1]*len(nums)max_dp 1max_i 0# results [[]]*len(nums) # 不能这样写这是浅拷贝results [[] for _ in range(len(nums))] # 记录以s[i]结尾的最长递增子序列for i in range(len(nums)):for j in range(i,-1,-1): # 检查i之前所有序列if nums[i] nums[j]: # 前提是s[i]大于s[j]if dp[i] dp[j] 1: # 次之是序列长度要更长因为存在相等的情况所以存在答案不唯一dp[i] dp[j] 1results[i] copy.deepcopy(results[j]) # 注意这里一定要用深拷贝# results[i] results[j][:] # 注意这里一定要用深拷贝results[i].append(nums[i])if max_dp dp[i]:max_dp dp[i]max_i ireturn (dp[max_i], results[max_i]) 6. 最长回文字符串
给你一个字符串 s找到 s 中最长的回文字符串。
示例
输入s babad
输出bab 解释aba 同样是符合题意的答案。
本题采用二维 dp 作为中间存储数据结构dp[i,j] 表示 s[i] 到 s[j] 是否为回文字符串主对角线表示每个单独的字符均为长度 1 的回文字符如果首尾两个元素相等中间部分也是回文字符串那当前字符串也为回文字符串所以递推公式为 dp[i,j] dp[i1,j-1] and s[i]s[j]从递推公式可以得到遍历输出是 i 从大到小 j 从小到大至此可以获取任意字符串是否为回文字符串。在遍历的同时记录下最长长度和对应的起止点。
def longest_palindrome(s):dp [[True]*len(s) for _ in range(len(s))] # 注意深浅拷贝问题直接相乘属于浅拷贝max_len 1max_beign 0max_end 0for i in range(len(s)-2, -1, -1):for j in range(i1, len(s)):dp[i][j] dp[i1][j-1] and s[i]s[j]if dp[i][j] and max_len j-i1: # 记录最长长度和对应起始终止位置max_len j-i1max_beign imax_end jreturn (max_len, s[max_beign:max_end1])
本题还可以采用中心扩展法即定义一个函数可以实现通过两边扩展遍历的方式寻找最长回文字符串返回回文字符串的长度和起始点然后遍历所有字符检查每个字符对应的最长回文字符串即可获取最长回文字符串。暴力遍历法的时间复杂度是O3空间复杂度是O1而动态规划的时间复杂度是O2空间复杂度是O1最后中心扩展法的时间复杂度是O2空间复杂度是O1。
def longest_palindrome(s):def check(s, i, j): # 检查从i和j向两边扩散的字符串是否是回文字符串while i0 and jlen(s) and s[i]s[j]: # 实际仅仅用于 ij 或者 ij-1 两种情况i - 1j 1return j-i-1, i1, j-1 # 返回回文字符串的长度和起始以及终止点max_len 1max_beign 0max_end 0for i in range(len(s)):len1, left1, right1 check(s, i, i)len2, left2, right2 check(s, i, i1)if max_len max(len1, len2):max_len max(len1, len2)if len1 len2:max_beign left1max_end right1else:max_beign left2max_end right2 return s[max_beign:max_end1] 7. 机器人路径条数
一个机器人位于一个 mxn 网格的左上角起始点在上图中标记为 “Start” 。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角在下图中标记为 “Finish”。问总共有多少条不同的路径
示例
输入m3, n7
输出28
本问题需要准备一个二维的 dp 数据结构记录中间过程dp[i,j] 表示从起点到 (i,j) 位置的路径条数dp[-1,-1]即为最终结果。那递推公式显然就是 dp[i,j]dp[i-1,j]dp[i,j-1]。初始条件第一行和第一列全部为1递推顺序是第二行开始从左到右从上到下。 def uniquePaths(m, n):dp [[1 for _ in range(n)] for _ in range(m)]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] 8. 礼物的最大价值
在一个 mxn 的棋盘的每一格都放有一个礼物每个礼物都有一定的价值价值大于 0。你可以从棋盘的左上角开始拿格子里的礼物并每次向右或者向下移动一格、直到到达棋盘的右下角。给定一个棋盘及其上面的礼物的价值请计算你最多能拿到多少价值的礼物
示例
输入[ [1,3,1], [1,5,1], [4,2,1] ]
输出12 解释: 路径 1→3→5→2→1 可以拿到最多价值的礼物
本问题需要准备一个二维的 dp 数据结构记录中间过程dp[i,j] 表示从起点到 (i,j) 位置的最多礼物dp[-1,-1] 即为最终结果。那递推公式显然就是 dp[i,j]max(dp[i-1,j]dp[i,j-1])grid[i,j]。初始条件第一行和第一列全部为累计求和结果递推顺序是第二行开始从左到右从上到下。 def maxValue(grid):m, n len(grid), len(grid[0])dp [[grid[0][0] for _ in range(n)] for _ in range(m)]for i in range(1, m):dp[i][0] dp[i-1][0] grid[i][0]for j in range(1, n):dp[0][j] dp[0][j-1] grid[0][j]for i in range(1, m):for j in range(1, n):dp[i][j] max(dp[i-1][j], dp[i][j-1]) grid[i][j]return dp[-1][-1]
