一维动态规划精讲

讲述职业经历和感悟：职场技巧、行业动态或职业生涯规划 #生活乐趣# #生活分享# #生活故事精选# #生活感悟精选#

一、一维动态规划问题

    一维动态规划时间复杂度一般有O(n)和O(n^2)两种，时间复杂度取决于状态转移方程。

    1.如果第i个状态的确定需要利用前i-1个状态，即dp[i]由dp[i-1],dp[i-2],...,dp[0]的取值共同决定，那么此时的时间复杂度为O(n^2)。

如 leetcode139.单词拆分、leetcode300. 最长上升子序列、面试题 17.16. 按摩师

139. 单词拆分

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

说明：

拆分时可以重复使用字典中的单词。你可以假设字典中没有重复的单词。

示例 1：

输入: s = "leetcode", wordDict = ["leet", "code"]

输出: true

解释: 返回 true 因为 "leetcode" 可以被拆分成 "leet code"。

示例 2：

输入: s = "applepenapple", wordDict = ["apple", "pen"] 输出: true 解释: 返回 true 因为 "applepenapple" 可以被拆分成 "apple pen apple"。   注意你可以重复使用字典中的单词。

示例 3：

输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]

输出: false

dp[i]表示前i个字符是否可以被空格拆分为一个或多个在字典中出现的单词，是为true，否为false。显然，dp[i]取值取决于{(dp[i-1],s[i:i+1] in),(dp[i-2],s[i-1:i+1]),...,(dp[0],s[1:i+1]) }中是否有取值为true的，也就是说在确定dp[i]的取值时，需要遍历dp[0:i-1]，所以时间复杂度为O(n^2)。

class Solution:

def wordBreak(self, s, wordDict):

"""

:type s: str

:type wordDict: List[str]

:rtype: bool

"""

d={}

for i in range(len(wordDict)):

d[wordDict[i]]=1

dp=[False]*len(s)

if s[0] in d:

dp[0]=True

if len(s)==1:

return dp[0]

if s[0:2] in d or (s[0] in d and s[1] in d):

dp[1]=True

for i in range(2,len(s)):

for j in range(i-1,-1,-1):

if dp[j] and s[j+1:i+1] in d:

dp[i]=True

if s[0:i+1] in d:

dp[i]=True

return dp[len(s)-1]

---------------------------------------------我是分割线------------------------------------------------------------------------

300. 最长上升子序列

给定一个无序的整数数组，找到其中最长上升子序列的长度。

示例:

输入: [10,9,2,5,3,7,101,18] 输出: 4 解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。

说明:

可能会有多种最长上升子序列的组合，你只需要输出对应的长度即可。你算法的时间复杂度应该为 O(n2) 。

进阶: 你能将算法的时间复杂度降低到 O(n log n) 吗?

class Solution:

def lengthOfLIS(self, nums):

"""

:type nums: List[int]

:rtype: int

"""

if len(nums)==0:

return 0

if len(nums)==1:

return 1

dp=[1]*len(nums)

dp[0]=1

res=0

for i in range(1,len(nums)):

maxD=0

for j in range(i-1,-1,-1):

if nums[i]>nums[j]:

maxD=max(maxD,dp[j])

dp[i]=maxD+1

res=max(res,dp[i])

return res

---------------------------------------------我是分割线------------------------------------------------------------------------

2.如果第i个状态只取决于第i-1个状态或者第i-2个状态或者第i-1和第i-2个状态，也就是说dp[i]的取值由dp[i-1]，或者dp[i-2]或者dp[i-1]和dp[i-2]决定，而不是取决于其之前的每一个状态，此时的时间复杂度为O(n)。

如leetcode198. 打家劫舍、leetcode746. 使用最小花费爬楼梯、leetcode53. 最大子序和、leetcode121. 买卖股票的最佳时机

198. 打家劫舍

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。

示例 1:

输入: [1,2,3,1]

输出: 4

解释: 偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。

  偷窃到的最高金额 = 1 + 3 = 4 。

示例 2:

输入: [2,7,9,3,1]

输出: 12

解释: 偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。

  偷窃到的最高金额 = 2 + 9 + 1 = 12 。

class Solution:

def rob(self, nums):

"""

:type nums: List[int]

:rtype: int

"""

if len(nums)==0:

return 0

dp=[0]*len(nums)

dp[0]=nums[0]

if len(nums)==1:

return dp[0]

dp[1]=max(dp[0],nums[1])

for i in range(2,len(nums)):

dp[i]=max(dp[i-1],dp[i-2]+nums[i])

return dp[len(nums)-1]

网址：一维动态规划精讲 https://www.yuejiaxmz.com/news/view/823530

相关内容

二维动态规划空间优化
动态规划之0
动态规划
动态规划之空间优化与总结回顾
动态规划：空间优化技巧以及接龙型动态规划
动态规划的应用
动态规划在实际生活中的应用
算法动态规划01背包问题
动态规划的时间复杂度优化
动态规划的优化与高级应用

随便看看