LIS问题
连续子数组最大和
def maxSubArray(self, nums: List[int]) -> int:
for i in range(1,len(nums)):
nums[i] = max(nums[i-1]+nums[i],nums[i])
return max(nums)
最长连续递增子序列长度
def findLengthOfLCIS(self, nums: List[int]) -> int:
if not nums:
return 0
dp = [1] * len(nums)
for i in range(1,len(nums)):
if nums[i] > nums[i-1]:
dp[i] = dp[i-1] + 1
else :
dp[i] = 1
return max(dp)
最长递增子序列长度
解法一：DP
def lengthOfLIS(self, nums: List[int]) -> int:
if(not nums):
return 0
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)
[进阶] 解法二：贪心+二分
思路：数组d[len]表示长度为len的的子序列末尾最大值,遍历数组时用二分查找得到插入d的位置
举例：[0, 8, 4, 12, 2]第一步插入 0，d = [0]
第二步插入 8，d = [0, 8]
第三步插入 4，d = [0, 4]
第四步插入 12，d = [0, 4, 12]
第五步插入 2，d = [0, 2, 12]
最终得到最大递增子序列长度为 3
[再进阶] 输出该序列
思路：要输出序列，就要确定序列的最大值，然后从后向前遍历数组
解法一知道以每个元素结尾的最长子序列长度
解法二知道固定长度子序列结尾的最小值
结合这两个信息就可以还原最长子序列
def LIS(arr):
if not arr: return None
n = len(arr)
d = [arr[0]]
dp = [1] * n # 记录以元素 arr[i] 结尾的最长递增子序列的长度
length = 1
for i in range(1,n): # 从1开始遍历
if arr[i] > d[-1]:
d.append(arr[i])
length += 1
dp[i] = length
else:
# 使用bisect库
index = bisect.bisect(d,arr[i])
dp[i] = index + 1 # 找到的是下标，长度需要再加1
d[index] = arr[i] # 插入到对应位置
# 手动实现二分
l, r = 0, len(d)-1
loc = -1
while (l <= r):
mid = (l+r)//2
if (arr[i] <= d[mid]):
loc = mid
r = mid - 1
else:
l = mid + 1
dp[i] = loc + 1
d[loc] = arr[i]
ans = []
max_val = d[-1]
count = len(d)
idx = arr.index(max_val)
for i in range(idx,-1,-1):
if not ans or (arr[i] < ans[-1] and dp[i] == count):
ans.append(arr[i])
count -= 1
return ans[::-1]
回文问题
最长回文子串(长度)
def longestPalindrome(s) ：
N = len(s)
if N == 1:
return s
dp = [[False for _ in range(N)] for _ in range(N)]
for i in range(N):
dp[i][i] = True
max_len,start = 1,0
for j in range(1,N): #因为后面外层j-1所以j要从1开始
for i in range(j): # i一定是小于j的，所以是循环到j
if(s[i] == s[j]):
if(j-i<3): #为什么这里是3 i+1 和 j-1 的距离小于1 j-1-(i+1)<1其实也就是 i+1和j-1相等，是一个字符的时候，肯定满足回文
dp[i][j]=True
else:
dp[i][j] = dp[i+1][j-1]
if(dp[i][j]):
l = j - i + 1
if(l > max_len):
max_len = l
start = i
return s[start:start+max_len]
这道题要注意一个比较重要的点，至少对我来说比较重要，就是在写二重循环的时候，为什么是先遍历j 然后再遍历i , 我们看下我们的思路中的这个公式 dp[i][j] = dp[i+1][j-1] 要有了后面的值才能赋值给前面，从这个二维矩阵就可以看出，列是外层循环，i是内层循环，这样就不会出错了
最长回文子序列长度
def longestPalindromeSubseq(self, s: str) -> int:
n=len(s)
dp=[[0]*n for _ in range(n)] #定义动态规划状态转移矩阵
for i in range(n): # 初始化对角线，单个字符子序列就是1
dp[i][i]=1
for i in range(n-1,-1,-1): #从右下角开始往上遍历 注意这里是n-1不是n
for j in range(i+1,n):
if s[i]==s[j]: #当两个字符相等时，直接子字符串加2
dp[i][j]= dp[i+1][j-1]+2
else: #不相等时，取某边最长的字符
dp[i][j]=max(dp[i][j-1],dp[i+1][j])
return dp[0][-1] #返回右上角位置的状态就是最长
221 最大正方形 字节
思路已经有了，但是最后有的case没有通过，还不知道为什么
def maximalSquare(self, matrix: List[List[str]]) -> int:
if not matrix: return 0
r,c = len(matrix),len(matrix[0])
if r == 0 or c == 0 : return 0
dp = [[int(matrix[i][j]) for j in range(c)] for i in range(r)]
fr,fc = dp[0], [dp[i][0] for i in range(r)]
l = max(max(fr),max(fc))
for i in range(1,r):
for j in range(1,c):
tmp = dp[i-1][j-1]
if(matrix[i][j]=='1' and tmp>0):
flag = True
index = 0
while index < tmp:
if matrix[i-index-1][j] == '0' or matrix[i][j-index-1] == '0':
flag = False
break
index += 1
if flag:
dp[i][j] = dp[i-1][j-1] + 1
else:
dp[i][j] = dp[i-1][j-1]
l = max(l,dp[i][j])
return l*l
和正确答案对比一下, 如何巧妙地把边界条件包含在循环中而不是单独判断
def maximalSquare(self, matrix: List[List[str]]) -> int:
if len(matrix) == 0 or len(matrix[0]) == 0:
return 0
maxSide = 0
rows, columns = len(matrix), len(matrix[0])
dp = [[0] * columns for _ in range(rows)]
for i in range(rows):
for j in range(columns):
if matrix[i][j] == '1':
if i == 0 or j == 0:
dp[i][j] = 1
else:
dp[i][j] = min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1
maxSide = max(maxSide, dp[i][j])
maxSquare = maxSide * maxSide
return maxSquare
1024. 视频拼接
这道题其实DP的思路不是很好想, 感觉贪心更好想
用dp[i]表示覆盖[0,i)需要的最小空间数
def videoStitching(self, clips: List[List[int]], T: int) -> int:
l = len(clips)
dp = [0] + [l+1]*T #0一定是0了，其他初始化一个不可能的大数len(clips)+1
for i in range(1,T+1):
for aj,bj in clips:
if aj < i <= bj: #[0,i)的后面部分可以被覆盖
#如果用这个部分覆盖，数目为dp[aj]+1 不用就是dp[i] 取最小值
dp[i] = min(dp[i],dp[aj]+1)
return -1 if dp[T]==l+1 else dp[T]
139. 单词拆分
继续动态规划
1. 72. 编辑距离
def minDistance(self, word1: str, word2: str) -> int:
m = len(word1)
n = len(word2)
#这里注意初始化的二维数组的时候，哪个在里面，哪个在外面
dp = [[0 for _ in range(n+1)] for _ in range(m+1)]
for i in range(m+1):
dp[i][0] = i
for j in range(n+1):
dp[0][j] = j
for i in range(1,m+1):
for j in range(1,n+1):
if(word1[i-1]==word2[j-1]):
dp[i][j]=dp[i-1][j-1]
else:
dp[i][j]=min(dp[i-1][j]+1,dp[i][j-1]+1,dp[i-1][j-1]+1)
return dp[-1][-1]
2.198. 打家劫舍
def rob(self, nums: List[int]) -> int:
N = len(nums)
if not nums:
return 0
if N == 1 : return nums[0]
if N == 2 : return max(nums[0],nums[1])
dp = list(range(N))
dp[0] = nums[0]
dp[1] = max(nums[0],nums[1])
for i in range(2,len(nums)):
dp[i] = max(dp[i-2] + nums[i], dp[i-1])
return dp[-1]
3.213. 打家劫舍 II
怎么能想到把这问题拆分成 只抢第一家 和 只抢最后一家 两个子问题？？？
def rob(self, nums: List[int]) -> int:
N = len(nums)
if not nums : return 0
if N <= 2 : return max(nums)
def helper(nums):
if len(nums) <= 2 : return max(nums)
dp = [0] * len(nums)
dp[0] = nums[0]
dp[1] = max(nums[0],nums[1])
for i in range(2,len(nums)):
dp[i]=max(dp[i-1],dp[i-2]+nums[i])
return dp[-1]
return max(helper(nums[1:]),helper(nums[:-1]))
2 72. 编辑距离
我看到“方法一”三个字的时候，惊喜地以为还有方法二。。没有，这次真没有。动态规划是个好东西，但难就难在如何定义DP数组里值的含义。听我来给你捋一捋。
啥叫编辑距离？我们说word1和word2的编辑距离为X，意味着word1经过X步，变成了word2，咋变的你不用管，反正知道就需要X步，并且这是个最少的步数。
我们有word1和word2，我们定义dp[i][j]的含义为：word1的前i个字符和word2的前j个字符的编辑距离。意思就是word1的前i个字符，变成word2的前j个字符，最少需要这么多步。
例如word1 = "horse", word2 = "ros"，那么dp[3][2]=X就表示"hor"和“ro”的编辑距离，即把"hor"变成“ro”最少需要X步。
如果下标为零则表示空串，比如：dp[0][2]就表示空串""和“ro”的编辑距离
定理一：如果其中一个字符串是空串，那么编辑距离是另一个字符串的长度。比如空串“”和“ro”的编辑距离是2（做两次“插入”操作）。再比如"hor"和空串“”的编辑距离是3（做三次“删除”操作）。
定理二：当i>0,j>0时（即两个串都不空时）dp[i][j]=min(dp[i-1][j]+1,dp[i][j-1]+1,dp[i-1][j-1]+int(word1[i]!=word2[j]))。
啥意思呢？举个例子，word1 = "abcde", word2 = "fgh",我们现在算这俩字符串的编辑距离，就是找从word1，最少多少步，能变成word2？那就有三种方式：
知道"abcd"变成"fgh"多少步（假设X步），那么从"abcde"到"fgh"就是"abcde"->"abcd"->"fgh"。（一次删除，加X步，总共X+1步）
知道"abcde"变成“fg”多少步（假设Y步），那么从"abcde"到"fgh"就是"abcde"->"fg"->"fgh"。（先Y步，再一次添加，加X步，总共Y+1步）
知道"abcd"变成“fg”多少步（假设Z步），那么从"abcde"到"fgh"就是"abcde"->"fge"->"fgh"。（先不管最后一个字符，把前面的先变好，用了Z步，然后把最后一个字符给替换了。这里如果最后一个字符碰巧就一样，那就不用替换，省了一步）
以上三种方式算出来选最少的，就是答案。所以我们再看看定理二：
dp[i][j]=min(dp[i-1][j]+1,dp[i][j+1]+1,dp[i][j]+int(word1[i]!=word2[j]))
dp[i-1][j]：#情况一
dp[i][j-1]+1：#情况二
dp[i-1][j-1]+int(word1[i]!=word2[j])：#情况三
有了定理二的递推公式，你就建立一个二维数组，考虑好空串的情况，总会写出来
进阶
先把二维数组的方法做出来，要还没做出来呢，先别往下看。
由定理二可知，dp[i][j]只和dp[i-1][j],dp[i][j-1],dp[i-1][j-1]三个量有关，即二维数组中，当前元素的左边，上边，左上角三个元素。
那我们不用这么大的二维数组存啊！我们就用一维数组，表示原来二维数组中的一行，然后我们就反复覆盖里面的值。dp[i-1][j]就是我当前左边的元素，dp[i][j-1]是没覆盖前我这里的值，dp[i-1][j-1]好像找不见了？那我们就单独用一个变量存着它，我们把它叫lu（left up），则代码为：
class Solution:
def minDistance(self, word1: str, word2: str) -> int:
m=len(word1)
n=len(word2)
dp=list(range(n+1))
for i in range(m):
lu=dp[0]
dp[0]=i+1
for j in range(n):
dp[j+1],lu=min(dp[j]+1,dp[j+1]+1,lu+int(word1[i]!=word2[j])),dp[j+1]
return dp[-1]
5. 16. 最接近的三数之和
有了之前3数之和的经验，这个还是解答起来比较简单的
def threeSumClosest(self, nums: List[int], target: int) -> int:
nums.sort()
distance = pow(10,4)
res = 0
for i in range(len(nums)):
low, high = i + 1, len(nums)-1
while(low < high):
sum_value = nums[i] + nums[low] + nums[high]
if abs(sum_value-target) < distance:
distance = abs(sum_value-target)
res = sum_value
if (sum_value > target):
high -= 1
elif (sum_value == target):
return target
else:
low += 1
return res
6. 454. 四数相加 II
这题目用我大python有点牛逼了。。。也太简洁明快了
def fourSumCount(self, A: List[int], B: List[int], C: List[int], D: List[int]) -> int:
record = collections.Counter(a + b for a in A for b in B)
return sum(record.get(- c - d, 0) for c in C for d in D)
4. 剑指 Offer 60. n个骰子的点数
这确定是个简单题目么。。。？感觉还是有点复杂的，
从题解来看，刷到了第一个动态规划的题目。那么我们来理一下DP问题的思路吧
- 首先要确定如何表示状态 用dp[n][j]表示投掷完 n 枚骰子后，点数 j 的出现次数
- 然后找出状态转移方程，dp[n][j] = dp[n-1][j-1] + ... dp[n-1][j-6]
- 最后确定边界条件 投掷完 1 枚骰子后,点数从1到6各出现一次 dp[1][i]=1
def twoSum(self, n: int) -> List[float]:
dp = [ [0 for _ in range(6*n+1)] for _ in range(n+1)] #如何初始化一个n行6n列的二维数组
for i in range(1,7):
dp[1][i] = 1
for i in range(2,n+1):
for j in range(i,i*6+1):
for k in range(1,7):
if(j>k):
dp[i][j]+=dp[i-1][j-k]
res = []
for i in range(n,6*n+1):
res.append(dp[n][i]*1.0/6**n)
return res
反复品了一下，好像又没有那么难，重点在于思路、套路
5. 剑指 Offer 49. 丑数
1003am-1023am
有事耽误了几天，看了下答案，好吧，表示自己真得想不出来 mark
三指针动态规划问题
def nthUglyNumber(self, n: int) -> int:
dp, a, b, c = [1] * n, 0, 0, 0
for i in range(1, n):
n2, n3, n5 = dp[a] * 2, dp[b] * 3, dp[c] * 5
dp[i] = min(n2, n3, n5)
if dp[i] == n2: a += 1
if dp[i] == n3: b += 1
if dp[i] == n5: c += 1
return dp[-1]
