塞进裤子ヾ(≧O≦)〃嗷~

0%

动态规划

模版

Re:https://labuladong.gitbook.io/algo/dong-tai-gui-hua-xi-lie/dong-tai-gui-hua-xiang-jie-jin-jie

1
2
3
4
5
6
7
8
9
10
#建立dp数组
dp = [minvalue or maxvalue]*n
#初始化base
dp[0] = 0 or othervalue
#进行状态转移
for i in range(n):#对每个状态,从1~n
for coin in coins:#对每种选择(以凑零钱为例子,要求最少的硬币数目)
if i - coin < 0:#判断选择是否合理
continue
dp[i] = min(dp[i],1+dp[i-coin])#状态转移方程

编辑距离

假设d[i][j]表示 str1[0]~str1[i-1]str2[0]~str2[j-1]`之间的最小编辑距离

  • s1=abf,s2=def,f相同,只要处理ab和de就行,d(3,3)=d(2,2)

  • s1=abc, s2=def,假设采用insert,向s1末尾插入f,s1=abcf,s2=def

    d(i,j) = d(i,j-1)+1 (1是insert的成本),

    d(i,j-1)表示将abc转换成de的最小编辑距离。

  • s1=abc, s2=def,假设采用delete,删除s1末尾,s1=ab,s2=def

    d(i,j) = d(i-1,j)+1 (1是delete的成本)

    d(i-1,j)表示将ab转换成def的最小编辑距离。

  • s1=abc, s2=def,假设采用replace,向s1末尾替换成f,s1=abf,s2=def

    为了保证最后一个字符相同,向s1末尾替换成f,s1=abf,s2=def

    d(i,j) = d(i-1,j-1)+1 (1是replace的成本)

    d(i-1,j-1)表示将ab转换成de的最小编辑距离。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def editDist(str1,str2):
m, n = len(str1), len(str2)
# 创建二维数组,
dp = [ [0 for i in range(n+1)] for j in range(m+1)]

for i in range(m+1):
for j in range(n+1):
if i == 0:#str1为空,转换代价为j(j次insert)
dp[i][j] = j
elif j == 0:#同理,第二个str为空,转换代价为i
dp[i][j] = i
elif str1[i-1] == str2[j-1]:#字符相同,不会产生代价
dp[i][j] = dp[i-1][j-1]
else:
dp[i][j] = 1+min(dp[i][j-1], #insert
dp[i-1][j], #delete
dp[i-1][j-1]) #replace
return dp[m][n]


str1="abc"
str2="def"
print(editDist(str1,str2))

RE:

https://www.cnblogs.com/yulinfeng/p/7096882.html

https://blog.csdn.net/ac540101928/article/details/52786435?depth_1-utm_source=distribute.pc_relevant.none-task&utm_source=distribute.pc_relevant.none-task

最大子序和

问题定义:

给定K个整数组成的序列{ N1, N2, …, NK },“连续子列”被定义为{ Ni, Ni+1, …, Nj },其中 1≤i≤j≤K。“最大子列和”则被定义为所有连续子列元素的和中最大者。

例如给定序列{ -2, 11, -4, 13, -5, -2 },其连续子列{ 11, -4, 13 }有最大的和20。现要求你编写程序,计算给定整数序列的最大子列和。

$$ sum[i] = max( sum[i-1]+data[i], data[i] ) $$

$sum[i] $ 表示以第i个数字结尾的子数组的最大和 ,不一定是整体的最大值。

注意$ data[i]<0$ 时 , $ sum[i] < sum[i-1] $

比如 【10,8,-5】的sum数组为【10,18,13】,其最大子序和为18

1
2
3
4
5
6
7
8
9
10
11
def maxSubArray(array):
if not array or len(array)==0:
return
curmax = 0 #以当前元素结尾的子序和最大值
maxsum = -9999 #sum[]中的最大值
for elem in array:
curmax = max(curmax+elem,elem)
maxsum = max(curmax, maxsum)
return maxsum

maxSubArray([10,8,-5,-2,9])

礼物的最大价值

https://sbaban.com/jzo47.html

最长不包含重复字符的子字符串

https://sbaban.com/jzo48.html

n个骰子的点数

https://sbaban.com/jzo60.html

剪绳子

https://sbaban.com/jzo14.html

if help:小手一抖点个广告 or 大手一挥资助一下