算法（动态规划（更新中））

恢弘志士之气，不宜妄自菲薄。这篇文章主要讲述算法：动态规划（更新中）相关的知识，希望能为你提供帮助。

【算法（动态规划（更新中））】

文章图片

1. 动态规划概述

特点：最优子结构性质（问题的最优解包含子问题的最优解）、重叠子问题

2. 最长公共子序列问题（LCS）

最长公共子序列即一个序列 S ，如果分别是两个或多个已知序列的子序列，且是所有符合此条件序列中最长的，则 S 称为已知序列的最长公共子序列。该子序列中每个元素不需要在序列中连续或相邻。

要解决最长公共子序列问题，最简单粗暴的方法就是穷举法，但对于一个长度为n的序列，其子序列的个数就有2n2^n2n个，因此需要对其进行简化。
解决该问题可以从子序列的前缀看起。其中c[i,j]表示长度为i和长度为j的两序列的最大公共子序列长度。

文章图片

但采用此种方法仍会有很多重复计算：

文章图片

对于重复的计算可以保存下来，在使用时，直接调用即可，将子问题的规模减小为m*n。这种方法在动态规划中被称为备忘法。
如何利用计算出的结果，可以将结果保存在数组中，也可以用自底向上的方法进行计算。
采用自底向上的计算方法，其代码如下所示：

class Solution {
public:
int longestCommonSubsequence(string text1, string text2) {
int len1=text1.length();
int len2=text2.length();
int a[len1+1][len2+1];
int i,j;
for(i=0; i< =len1; i++)//初始化数组
a[i][0]=0;
for(j=0; j< =len2; j++)
a[0][j]=0;
for(i=0; i< len1; i++){
for(j=0; j< len2; j++){
if(text1[i]==text2[j]){
a[i+1][j+1]=a[i][j]+1;
}
else{
a[i+1][j+1]=max(a[i][j+1],a[i+1][j]);
}
}
}
return a[len1][len2];

}
};

3. 最大子序和问题

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
示例:
输入: [-2,1,-3,4,-1,2,1,-5,4]
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/maximum-subarray
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

这道题其实用分治算法也能解决，参见我的??上一篇博客??，这里用动态规划的方法求解，定义以第i个数为结尾的最大子序和为a[i]，则该数组的最大子序和为a[i]中的最大值，而a[i]具有如下关系：a[i]=max(a[i?1]+nums[i],nums[i])a[i]=max(a[i-1]+nums[i],nums[i])a[i]=max(a[i?1]+nums[i],nums[i])利用该关系可以通过自底向上得出结果。

class Solution {
public:
int maxSubArray(vector< int> & nums) {
int len = nums.size();
int a[len];
a[0]=nums[0];
int sum=nums[0];
for(int i=1; i< len; i++){
if(a[i-1]> 0)
a[i]=a[i-1]+nums[i];
else
a[i]=nums[i];
if(a[i]> sum)
sum=a[i];
}
return sum;

}

};