一、一维动态规划问题
一维动态规划时间复杂度一般有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循环，时间复杂度O(n^2)
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
) 吗?
#思路：动态规划，时间复杂度O(n^2)。切记：不要添加无关的打印语句。。。，不然会超时
#dp[i]表示以第i个数为结尾的序列的长度
#显然，dp[i]的值取决于(dp[i-1],dp[i-2],...,dp[0])中最大的且满足nums[i]大于nums[j],j=i-1,i-2,...,0.
#所以时间复杂度为O(n^2)
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])
#状态转移方程 时复杂度O(n)
for i in range(2,len(nums)):
dp[i]=max(dp[i-1],dp[i-2]+nums[i])
return dp[len(nums)-1]