算法&数据结构（七）：动态规划

理解动态规划：

将一个问题拆成几个子问题，分别求解这些子问题，即可推断出大问题的解。

求解时，需要设计状态函数，转移方程。

 

leetcode：300. 最长上升子序列

问题描述：给定一个无序的整数数组，找到其中最长上升子序列的长度

解法一：动态规划

思路：遍历数组的每个元素，如果当前元素大于在他前面的任何一个元素，状态转移方程为 if n-1 < n, f(n) = f(n-1) + 1

时间复杂度：O(n*n)

class Solution: def lengthOfLIS(self, nums: List[int]) -> int: # 注意处理异常输入 if nums == []: return 0 # 状态转移方程为 if n-1 < n, f(n) = f(n-1) + 1 n = [1] * len(nums) # 遍历每个元素，从1开始 for i in range(1, len(nums)): # 分别与在它之前的元素相比较 for j in range(i): # if n-1 < n, f(n) = f(n-1) + 1 if nums[j] < nums[i]: n[i] = max(n[i], n[j] + 1) return max(n)

解法二：贪心算法 + 二分查找

思路：如果后续的元素大于数组末尾的元素，则接在末尾；否则找到第一个大于等于元素的值，然后替换

时间复杂度：O(nlog⁡n)

class Solution(object): def lengthOfLIS(self, nums): if len(nums) < 2: return len(nums) tail = [nums[0]] for i in range(1, len(nums)): # 如果后续的元素大于数组末尾的元素，则接在末尾 if nums[i] > tail[-1]: tail.append(nums[i]) continue # 找到第一个大于等于元素的值，然后替换 left = 0 right = len(tail) - 1 while left < right: mid = (left + right) >> 1 if tail[mid] < nums[i]: left = mid + 1 else: right = mid tail[left] = nums[i] return len(tail)

 

leetcode：121. 买卖股票的最佳时机

问题描述：给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。如果你最多只允许完成一笔交易（即买入和卖出一支股票），设计一个算法来计算你所能获取的最大利润。

解法：只能买卖一次，定义状态转移方程——买 buy = max(buy, -price[i]) ； 卖 sell = max(sell, prices[i] + buy)

时间复杂度：O(n)

class Solution: def maxProfit(self, prices: List[int]) -> int: if prices == []: return 0 buy = -prices[0] sell = 0 for i in range(len(prices)-1): buy = max(buy, -prices[i]) sell = max(sell, buy + prices[i+1]) return sell

leetcode：122. 买卖股票的最佳时机 II

问题描述：计算你所能获取的最大利润。尽可能地完成更多的交易（多次买卖一支股票）注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）

解法：可以多次买卖，买入状态之前可拥有卖出状态，所以买入的转移方程需要变化。买 buy = max(buy, sell-price[i])

时间复杂度：O(n)

class Solution: def maxProfit(self, prices: List[int]) -> int: if prices == []: return 0 buy = -prices[0] sell = 0 for i in range(len(prices)): # 买入的状态需要加上卖出时得到的利润 buy = max(buy, sell - prices[i]) sell = max(sell, buy + prices[i]) return sell

leetcode：123. 买卖股票的最佳时机 III

问题描述：设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。

解法：如果当天买入再卖出，收益为0，即买卖的价格元素下标一致；

第一次买 buy_1 = max(buy_1, -price[i]) ； 第一次卖 sell_1 = max(sell_1, prices[i] + buy_1)

第一次买 buy_2 = max(buy_2, sell_1 - price[i]) ； 第一次卖 sell_2 = max(sell_2, prices[i] + buy_2)

时间复杂度：O(n)

class Solution: def maxProfit(self, prices: List[int]) -> int: if prices == []: return 0 buy_1 = -prices[0] buy_2 = -prices[0] sell_1 = 0 sell_2 = 0 for i in range(len(prices)): buy_1 = max(buy_1, -prices[i]) sell_1 = max(sell_1, buy_1 + prices[i]) buy_2 = max(buy_2, sell_1 - prices[i]) sell_2 = max(sell_2, buy_2 + prices[i]) return sell_2

leetcode：72. 编辑距离

问题描述：给定两个单词 word1 和 word2，计算出将 word1 转换成 word2 所使用的最少操作数 

解法：假设序列S、T长度为m、n，编辑距离为edit[m][n]

当前元素相同—— edit[m][n] = edit[m-1][n-1]

插入一个字符—— edit[m][n] = edit[m-1][n] + 1 = edit[m][n-1] + 1

删除一个字符—— edit[m][n] = edit[m-1][n] + 1 = edit[m][n-1] + 1

替换一个字符—— edit[m][n] = edit[m-1][n-1] + 1

特殊情况——        edit[0][n] = n     edit[m][0] = m

时间复杂度：O(mn)，两层循环显而易见

class Solution: def minDistance(self, word1: str, word2: str) -> int: m = len(word1) n = len(word2) # (m + 1)行、 (n + 1)列 d = [[0] * (n + 1) for _ in range(m + 1)] # 特殊情况：至少有一个空字符串 if m * n == 0: return max(m, n) for i in range(m + 1): d[i][0] = i for j in range(n + 1): d[0][j] = j for i in range(1, m + 1): for j in range(1, n + 1): if word1[i-1] == word2[j-1]: cost = 0 else: cost = 1 d[i][j] = min(d[i-1][j-1] + cost, d[i-1][j] + 1, d[i][j-1] + 1) return d[m][n]

leetcode：62. 不同路径

问题描述：一个机器人位于一个 m x n 网格的左上角。每次只能向下或者向右移动一步，问总共有多少条不同的路径？

解法：动态规划

时间复杂度：O(m*n)

class Solution: def uniquePaths(self, m: int, n: int) -> int: # 动态规划 if m <= 0 and n <= 0: return 0 # 注意初始值！！！ dp = [[1] * 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[m-1][n-1]

企业真题：最长公共连续字串——两个字符串（可能包含空格）,找出其中最长的公共连续子串，并输出其长度。

解法：当str1[i] == str2[j]时，m[i + 1][j + 1] = m[i][j] + 1；当str1[i] != str2[j]时，m[i + 1][j + 1] = 0

然而如果求解最长公共子序列则不要求连续，当str1[i] != str2[j]时，m[i + 1][j + 1] = max( m[i][j + 1], m[i + 1][j] )

# 最长公共连续字串 def find_string(s1, s2): dp = [[0] * (len(s2)+1) for _ in range(len(s1)+1) ] l_max = 0 for i in range(len(s1)): for j in range(len(s2)): if s1[i] == s2[j]: dp[i+1][j+1] = dp[i][j] + 1 if dp[i+1][j+1] > l_max: l_max = dp[i+1][j+1] return l_max # 最长公共子序列 def find_sequence(s1, s2): dp = [[0] * (len(s2) + 1) for _ in range(len(s1) + 1)] l_max = 0 for i in range(len(s1)): for j in range(len(s2)): if s1[i] == s2[j]: dp[i + 1][j + 1] = dp[i][j] + 1 else: dp[i + 1][j + 1] = max(dp[i][j + 1], dp[i + 1][j]) if dp[i + 1][j + 1] > l_max: l_max = dp[i + 1][j + 1] return l_max print(find_string('abcde', 'abgde')) print(find_sequence('abcde', 'abgde'))

企业真题：n个数组成的数列，牛牛现在想取一个连续的子序列，满足：最多只改变一个数，使得连续的子序列是一个严格上升的子序列，牛牛想知道这个连续子序列最长的长度是多少。 

解法：从前往后，正向记录递增的长度；从后往前，反向记录递减的长度；对于范围 (1, len(line)-1) ，取正向和反向递增长度最大的，如果满足 line[i+1] - line[i-1] >= 2，则说明line[i]可以替换，计算 max(res, pre[i-1] + last[i+1] + 1)

# 牛牛的数组：最长连续升序的子序列长度（最多改变一个数） line =[6,7,2,3,1,5,6] pre = [1] * len(line) last = [1] * len(line) # 最小长度为1 res = 1 # 从前往后，正向记录递增的长度 for i in range(1, len(line)): if line[i] > line[i-1]: pre[i] = pre[i-1] + 1 else: pre[i] = 1 # print('pre = ', pre) # 从后往前，反向记录递减的长度 for i in range(len(line)-2,-1,-1): if line[i] < line[i+1]: last[i] = last[i+1] + 1 else: last[i] = 1 # print('last = ', last) # 范围 (1, len(line)-1) for i in range(1, len(line)-1): # 取正向和反向递增长度最大的 res = max(res, pre[i]) res = max(res, last[i]) # 如果前后的数相差>=2，则可以替换 if line[i+1] - line[i-1] >= 2: res = max(res, pre[i-1] + last[i+1] + 1) print(res)

leetcode：139. 单词拆分

问题描述：给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。

解法：动态规划，flag[i]表示到第i-1个字符时，是否为能被拆分为字典里的单词

时间复杂度：O(N*N)

class Solution: def wordBreak(self, s: str, wordDict: List[str]) -> bool: if not wordDict: return False # flag[i]表示到第i-1个字符时，是否为能被拆分为字典里的单词 flag = [True] + [False] * len(s) # 当start为0时，从头到尾遍历一次，然后把能够拆分的位置标记为True。然后继续遍历可以拆分的位置 for start in range(len(s)): if flag[start]: for end in range(start + 1, len(s) + 1): print(s[start:end]) if s[start:end] in wordDict: flag[end] = True return flag[-1]

问题描述：求非连续数组的最大和，返回最大和组成元素的长度

解法：分解问题为选择前面一位数的结果 or 当前数字 + 前两位的数的结果 。res长度设置为(n+1)，res[1]为第一个数字，res[0]是用来保证循环的运行。注意：如果第二个数大于第一个数， count[i] = count[i-2] + 1，如果 count[0] = 0，那么 count[2] = 1，而不是 2 ！

代码：

# -*- coding:utf-8 -*- def rob(nums): n = len(nums) if n == 0: return 0, 0 res = [0] * (n + 1) # 第二个位置赋值为第一个数字 res[1] = nums[0] count = [0] * (n + 1) # 第一个位置不对应数字，第二个位置对应第一个数字 count[1] = 1 for i in range(2, n + 1): res[i] = max(res[i - 2] + nums[i-1], res[i - 1]) # 如果当前的最大和 大于 前一次的最大和 if res[i] > res[i-1]: count[i] = count[i-2] + 1 else: count[i] = count[i-1] return res[-1],count[-1] print(rob([1,7]))

leetcode：64. 最小路径和

问题描述：给定非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

说明：每次只能向下或者向右移动一步。

解法：左和上两个方向路径和的最小，再加上当前的数字

时间复杂度：O(N×N)

class Solution(object): def minPathSum(self, grid): """ :type grid: List[List[int]] :rtype: int """ # 行 m = len(grid) # 列 n = len(grid[0]) res = [[0] * n] * m for i in range(m): for j in range(n): # 同时存在左和上 if 0 <= i-1 < m and 0 <= j-1 < n: # 左和上两个方向路径和的最小，再加上当前的数字 res[i][j] = min(res[i-1][j], res[i][j-1]) + grid[i][j] # 上 elif 0 <= i-1 < m: res[i][j] = res[i-1][j] + grid[i][j] # 左 elif 0 <= j-1 < n: res[i][j] = res[i][j-1] + grid[i][j] # 没有左和上 else: res[i][j] = grid[i][j] return res[m-1][n-1]

leetcode：91. 解码方法

问题描述：一条包含字母 A-Z 的消息通过以下方式进行了编码：

'A' -> 1 'B' -> 2 ... 'Z' -> 26

给定一个只包含数字的非空字符串，请计算解码方法的总数

解法：动态规划，dp = df[i-1] + dp[i-2]，如果前一位字符和当前字符能组成[10,26]之间的数，即int(s[i-2:i])，则加上dp[i-2]；当前字符大于0，即int(s[i-1])，则加上dp[i-1]

时间复杂度：O(n)

def numDecodings(s): if s == '0': return 0 # 构造一个n+1 长度的数组 dp = [0] * (len(s) + 1) # 为了第二个元素方便计算 dp[0] = 1 # 代表第一个元素 dp[1] = int(s[0] != '0') for i in range(2, len(s)+1): # 如果前一位字符和当前字符，即int(s[i-2:i])，能组成[10,26]之间的数，则加上dp[i-2] # 当前字符int(s[i-1])，大于0，即则加上dp[i-1] dp[i] = dp[i-2] * int(9 < int(s[i-2:i]) < 27) + dp[i-1] * int(int(s[i-1]) > 0) return dp[-1] print(numDecodings('111')) # 思路 dp = df[i-1] + dp[i-2]

 

leetcode：

问题描述：

解法：

时间复杂度：

 

 

剑指offer：

问题描述：

解法：

时间复杂度：