1、 dp
1.1 0-1背包
01背包问题：
1、dp[i][j]定义：前i个物品，背包的最大价值或重量
2、递推公式：
(a) j>=v[i]时，dp[i][j] = max(dp[i-1][j], dp[i-1][j-v[i]] + w[i])
(b) j<v[i]时，dp[i][j] = dp[i-1][j]
3、边界条件：i=0或j=0时，dp[i][j] = 0
特别注意：由于dp多了一行和一列，读v[i]、w[i]时，用下标i-1
class Solution:
def knapsack(self , V , n , vw ):
# write code here
#print('V=',V)
#print('n=',n)
#print('vw=',vw)
dp = [[0]*(V+1) for _ in range(n+1)]
for i in range(n+1):
v_i = vw[i-1][0]
w_i = vw[i-1][1]
for j in range(V+1):
if i>0 and j>0:
if j >= v_i:
dp[i][j] = max(dp[i-1][j], dp[i-1][j-v_i] + w_i)
else:
dp[i][j] = dp[i-1][j]
# print(dp[-1][-1])
return dp[-1][-1]
1.2 带条件的0-1背包
https://www.nowcoder.com/practice/f9c6f980eeec43ef85be20755ddbeaf4?tpId=37&&tqId=21239&rp=1&ru=/ta/huawei&qru=/ta/huawei/question-ranking
w_max,n = map(int,input().strip().split())
w_max = w_max//10
#print('w_max=',w_max,'n=',n)
T = []
for i in range(n):
v,w,q = map(int,input().strip().split())
T.append([v//10,w*v//10,q])
#print('T=',T)
#==========================================
# 处理主件
W = [[] for _ in range(n)]
V = [[] for _ in range(n)]
I = []
for i in range(n):
if T[i][2]==0:
W[i].append(T[i][0])
V[i].append(T[i][1])
I.append(i)
#print('W=',W)
#print('V=',V)
#print('I=',I)
#==========================================
# 处理附件
for i in range(n):
if T[i][2]>0:
ii = T[i][2]-1
W[ii].append(T[i][0])
V[ii].append(T[i][1])
#print('W=',W)
#print('V=',V)
#==========================================
# 附件的排列组合
for i in range(n):
if len(W[i])==2:
W[i] = [W[i][0], W[i][0]+W[i][1]]
V[i] = [V[i][0], V[i][0]+V[i][1]]
if len(W[i])==3:
W[i] = [W[i][0], W[i][0]+W[i][1], W[i][0]+W[i][2], W[i][0]+W[i][1]+W[i][2]]
V[i] = [V[i][0], V[i][0]+V[i][1], V[i][0]+V[i][2], V[i][0]+V[i][1]+V[i][2]]
#print('W=',W)
#print('V=',V)
#==========================================
DP = [[0]*(w_max+1) for _ in range(len(I)+1)]
for i in range(1,len(I)+1):
ii = I[i-1]
for j in range(1,w_max+1):
t_max = DP[i-1][j]
for k in range(len(W[ii])):
W_i = W[ii][k]
V_i = V[ii][k]
if j>=W_i:
t_max = max(t_max, DP[i-1][j-W_i]+V_i)
DP[i][j] = t_max
#print('DP=',DP)
print(DP[-1][-1]*10)
1.3 最长增长子序列
dp = [1]*n
for i in range(1,n): # 第i个桩高度L[i]
for j in range(0,i): # 第0~i-1个桩调度L[0]~L[i-1]
if L[i]>L[j]: # 如果存在L[i]>L[j]则maxLen[i]需更新
dp[i] = max(dp[j]+1, dp[i]) # 在0<=j<=i-1中，保留更大的更新
print(dp)
1.4 最长回文子串
dp[i][j]定义为：如果dp[i][j]为1，则表示字符串从i到j是回文子串，
如果dp[i][j]为0，则表示字符串从i到j不是回文子串。
1、当i==j时，dp[i][j]==1
2、当j-i<=2时，如s[i]==s[j]，dp[i][j]==1
3、其它情况，如s[i]==s[j]，当dp[i+1][j-1]==1，则dp[i][j]==1
由于递推公式：
dp[i][j] = dp[i+1][j-1]==1，条件是s[i]==s[j]，i要从大的数值，j要从小的数值开始计算
dp = [[0]*n for _ in range(n)]
maxlen = 1
str1 = ''
for i in range(n-1,-1,-1):
for j in range(i,n):
if A[i]==A[j]:
if j-i<=2:
dp[i][j] = 1
else:
dp[i][j] = dp[i+1][j-1]
if dp[i][j]==1 and j-i+1>maxlen:
maxlen = j-i+1
str1 = A[i:j+1]
1.5 最长回文子序列
dp[i][j]定义为：字符串从i到j是含有回文子序列的长度
1、当i==j时，dp[i][j]==1
2、当j-i<=2时，如s[i]==s[j]，dp[i][j] = j-i+1
3、当j-i>2时, 如s[i]==s[j]，dp[i][j] = dp[i+1][j-1]+2
4、如s[i]!=s[j]时，dp[i][j] = max(dp[i][j-1], dp[i+1][j])
由于递推公式：
dp[i][j] = dp[i+1][j-1]+2，i要从大的数值，j要从小的数值开始计算
class Solution:
def longestPalindromeSubSeq(self, A, n):
# write code here
#print(A)
#print(n)
dp = [[0]*n for _ in range(n)]
for i in range(n-1,-1,-1):
for j in range(i,n):
if A[i]==A[j]:
if j-i<=2:
dp[i][j] = j-i+1
else:
dp[i][j] = dp[i+1][j-1]+2
else:
dp[i][j] = max(dp[i][j-1], dp[i+1][j])
#for i in dp:
# print(i)
return dp[0][-1]
print(max(dp)) # 对所有maxLen[i]取最大
1.6 最长公共子串
dp[i][j]定义为：str1在索引i处，str2在索引j处，存在公共子串的最大长度（即至少存在str1[i]==str2[j]）
需要记录所有的ij处存在公共子串的最大长度，及对应的i或j（子串终点）
1、当i==0 | j==0：
(a)当str1[i] == str2[j]，dp[i][j] = 1
2、其它情况：
(b)当str1[i] == str2[j]，dp[i][j] = dp[i-1][j-1] + 1
class Solution:
def LCS(self , str1 , str2 ):
# write code here
r = len(str1)
c = len(str2)
dp = [[0]*c for _ in range(r)]
maxlen = 0
endstr1 = 0
for i in range(r):
for j in range(c):
if (i==0 or j==0):
if str1[i]==str2[j]:
dp[i][j] = 1
else:
if str1[i]==str2[j]:
dp[i][j] = dp[i-1][j-1]+1
if dp[i][j]>maxlen:
maxlen = dp[i][j]
endstr1 = i
if maxlen>0:
return str1[endstr1-maxlen+1:endstr1+1]
1.7 最长公共子序列
dp[i][j]定义为：str1在索引i处及之前位置，str2在索引j处及之前位置，存在公共子序列的最大长度
需要回溯取依据取公共子序列字符
1、当i==0 | j==0：
(a)当str1[i] == str2[j]，dp[i][j] = 1
(b)当str1[i] != str2[j]，dp[i][j] = max(dp[i-1][j], dp[i][j-1])
2、其它情况：
(c)当str1[i] == str2[j]，dp[i][j] = dp[i-1][j-1] + 1
(d)当str1[i] != str2[j]，dp[i][j] = max(dp[i-1][j], dp[i][j-1])
class Solution:
def LCS(self , str1 , str2 ):
# write code here
if str1 == '' or str2 == '':
return '-1'
r = len(str1)
c = len(str2)
dp = [[0]*(c+1) for _ in range(r+1)]
for i in range(1,1+r):
for j in range(1,1+c):
if (i==1 or j==1):
#print('A--',i,j)
if str1[i-1]==str2[j-1]:
dp[i][j] = 1
else:
dp[i][j] = max(dp[i][j-1],dp[i-1][j])
else:
#print('B--',i,j)
if str1[i-1]==str2[j-1]:
dp[i][j] = dp[i-1][j-1]+1
else:
dp[i][j] = max(dp[i][j-1],dp[i-1][j])
i = r
j = c
substr = ''
while i>=1 and j>=1:
if str1[i-1]==str2[j-1]:
substr += str1[i-1]
i -= 1
j -= 1
else:
if dp[i-1][j]>dp[i][j-1]:
i -= 1
else:
j -= 1
#print(substr[::-1])
if substr != '':
return substr[::-1]
else:
return '-1'
1.8 最小编辑代价
动态规划
1.dp[i][j]定义
字符串str1[0~i]编辑成字符串str2[0~j]的需要的最小编辑代价
2.状态转移方程
当str2[i] == str1[j]，dp[i][j] = dp[i-1][j-1]
当str2[i] != str1[j]，dp[i][j] = min(dp[i][j-1]+ic, dp[i-1][j]+dc, dp[i-1][j-1]+rc) # 插入、删除、替换比小
3.边界
dp[0][0] = 0
dp[0][j] = j*ic，j次插入
dp[i][0] = i*dc，i次删除
r = len(str1)
c = len(str2)
dp = [[0]*(c+1) for _ in range(r+1)]
for i in range(r+1):
for j in range(c+1):
if i==0 and j==0:
dp[i][j]=0
elif i==0:
dp[0][j] = j*ic # j变化插入操作
elif j==0:
dp[i][0] = i*dc # i变量删除操作
else:
if str1[i-1]==str2[j-1]:
dp[i][j] = dp[i-1][j-1] # 对应字符相等则代价不变，如不等则需替换操作
else:
dp[i][j] = min(dp[i][j-1]+ic, dp[i-1][j]+dc, dp[i-1][j-1]+rc) # 插入、删除、替换比小
for i in dp:
print(i)
return dp[-1][-1]
1.9 子数组的最大累加和
t = 0
maxsum1 = 0
for i in arr:
t += i
if t<0:
t=0
elif t>maxsum1:
maxsum1 = t
1.10 子数组最大乘积
1、要同时记住每次乘积之后的最大，最小（比较时要含自己）
2、最大最小要存个临时变量以防覆盖
class Solution:
def maxProduct(self , arr ):
# write code here
#print(arr)
n = len(arr)
t_max = arr[0]
t_min = arr[0]
maxprod = arr[0]
for i in range(1,n):
t_max2 = max(t_max*arr[i], arr[i], t_min*arr[i])
t_min2 = min(t_max*arr[i], arr[i], t_min*arr[i])
t_max = t_max2
t_min = t_min2
if t_max > maxprod:
maxprod = t_max
return maxprod
1.11 矩阵的最小路径和
dp[i][j]定义为：从左上角到当前位置的最短路径，m[i][j]当前位置上的路径值，
核心迭代公式为，
dp[i][j] = min(dp[i][j-1],dp[i-1][j]) + m[i][j]
即，到当前位置的最短路径 = 从上和从左方向来的路径的最小值 + 当前位置上的路径值
dp = [[0]*c for _ in range(r)]
dp[0][0] = m[0][0]
for i in range(r):
for j in range(c):
if (i==0 and j>0):
dp[i][j] = dp[i][j-1] + m[i][j]
elif (j==0 and i>0):
dp[i][j] = dp[i-1][j] + m[i][j]
else:
dp[i][j] = min(dp[i][j-1],dp[i-1][j]) + m[i][j]
1.12 不同路径数
dp[i][j]表示前i行、j列的路径数，状态公式如下：
如果i >= 2 && j >= 2，那么dp[i][j] = dp[i-1][j] + dp[i][j-1]
dp[1][k] = 1
dp[k][1] = 1
解释如下：
当列数和行数大于2的时候，当前节点的路径数为左侧节点路径数+右侧节点路径数
当列数或行数为1时，当前节点的路径数恒为1
class Solution:
def uniquePaths(self , m , n ):
# write code here
dp = [[0]*n for _ in range(m)]
for i in range(m):
for j in range(n):
if (i==0 or j==0):
dp[i][j] = 1
else:
dp[i][j] = dp[i-1][j]+dp[i][j-1]
return dp[-1][-1]
1.13 最大正方形面积
1.确定dp[][]数组的含义
此题的dp[i][j]，代表以坐标为(i,j)的元素为右下角的正方形的边长。
2.状态转移方程
dp[i][j]的值取决于dp[i-1][j],dp[i-1][j-1],dp[i][j-1]的最小值
即左方正方形的边长，左上方正方形的边长，上方正方形的边长三者的最小值。
3.边界
由于状态转移方程中涉及i-1，j-1，所以i和j一定要大于0.
故dp[0][] 和 dp[][0]要首先确定。
class Solution:
def solve(self , matrix ):
m = matrix
r = len(m)
c = len(m[0])
dp = [[0]*c for _ in range(r)]
maxLen = 0
for i in range(r):
for j in range(c):
if (i==0 or j==0) and m[i][j]==1:
dp[i][j] = 1
elif m[i][j]==1:
dp[i][j] = min(dp[i-1][j-1],dp[i-1][j],dp[i][j-1])+1
if dp[i][j]>maxLen:
maxLen = dp[i][j]
#print('maxLen=',maxLen)
return maxLen*maxLen
1.14 把数字翻译成字符串
1.dp[i]定义
字符串 nums[0-i] 的可能的译码结果
2.状态转移方程
（i>=2）
（a）后两个字符11-19，21-26时，dp[i] = dp[i-1] + dp[i-2]
（b）当前字符1-9时，后两个字符10或20时，dp[i] = dp[i-1]
（c）其它情况 dp[i] = 0
3.边界
(i==0)
首字符1-9时，dp[0] = 1
首字符为0时，dp[0] = 0，直接返回
(i==1)
（a）后两个字符11-19，21-26时，dp[i] = 2
（b）当前字符1-9时，后两个字符10或20时，dp[i] = 1
（c）其它情况 dp[i] = 0
dp = [0]*n
for i in range(n):
if i==0:
if 1<=int(nums[i])<=9:
dp[i] = 1
else:
dp[i] = 0
return 0
elif i==1:
if 11<=int(nums[i-1:i+1])<=19 or 21<=int(nums[i-1:i+1])<=26:
dp[i] = 2
elif 1<=int(nums[i])<=9 or int(nums[i-1:i+1])==10 or int(nums[i-1:i+1])==20:
dp[i] = 1
else:
dp[i] = 0
else:
if 11<=int(nums[i-1:i+1])<=19 or 21<=int(nums[i-1:i+1])<=26:
dp[i] = dp[i-1] + dp[i-2]
elif 1<=int(nums[i])<=9 or int(nums[i-1:i+1])==10 or int(nums[i-1:i+1])==20:
dp[i] = dp[i-1]
else:
dp[i] = 0
京公网安备 11010502036488号