动态规划经典题目整理

朴灿烈づ我的快乐病毒、 2021-09-28 14:36 363阅读 0赞

### 动态规划经典题目整理 ###

*  背包问题
 *  最长公共子串问题
 *  连续数组最大和问题
 *  持续增加中。。。。

# 背包问题 #

复杂度  O ( n W ) O(nW) O(nW)  
 n n n为物品种类， W W W是背包的重量

目的：使得背包中的物品价值最大化

1.  单副本背包问题：（每种物品只有一件）  
     K ( w , j ) = m a x \{ K ( w − w j , j − 1 ) + v j , K ( w , j − 1 ) \} K(w,j)=max\\\{K(w-w\_j,j-1)+v\_j,K(w,j-1)\\\} K(w,j)=max\{ K(w−wj,j−1)\+vj,K(w,j−1)\}
    
     K ( w , j ) K(w,j) K(w,j)代表背包重量为 W W W，有 j j j件物品时候的最大价值  
     v j v\_j vj为第 j j j种物品的价值
2.  多副本背包问题：（每种物品有无数件）  
     K ( w ) = m a x \{ K ( w − w i ) + v i : w i < = w \} K(w)=max\\\{K(w-w\_i)+v\_i:w\_i<=w\\\} K(w)=max\{ K(w−wi)\+vi:wi<=w\}

# 最长公共子串问题 #

[博客入口][Link 1]  
问题描述： 设有 s \[ m \] s\[m\] s\[m\]，和 t \[ n \] t\[n\] t\[n\]两个字符串，要找他们最长的公共子串

解：  
设置一个变量 存储最长公共子串的长度  
`long=0;`

`c(i,j)=s[i]==s[j]?c(i-1,j-1)+1:0`  
每次如果 `c(i,j)>long` 那么 `long=c(i,j)`

设两个子序列的长度分别为 m m m, n n n  
那么时间复杂度就为 O ( m n ) O(mn) O(mn)

# 连续数组最大和问题 #

例子：  
给定一个数组如：  
`{-2, 11, -4, 13, -5, -2 }`  
该数组的最大和为 i=2, j=4的时候 11-4+13=20

算法:

int sum=0, b=0;
    
    for(int i=1;i<=n;++i){ 
    	if(b>0){ 
    		b+=a[i];
    	}
    	else{ 
    		b=a[i]
    	}
    	if(b>sum)
    		sum=b;
    }
    return sum;

复杂度： O ( n ) O(n) O(n)

# 持续增加中。。。。 #

[Link 1]: https://www.cnblogs.com/ider/p/longest-common-substring-problem-optimization.html