1. 最长公共子序列

假设 X 和 Y 的序列如下：

X[1...m] = {A, B, C, B, D, A, B}Y[1...n] = {B, D, C, A, B, A}

可以看出，X 和 Y 的最长公共子序列有 “BDAB”、“BCAB”、“BCBA”，即长度为4。

思路 : 动态规划

下面是用动态规划（打表）解决LCS问题：

// 动态规划求解LCS问题#include <iostream>#include <string>#include <vector>#include <algorithm>using namespace std;/*** 返回X[0...m-1]和Y[0...n-1]的LCS的长度 */int lcs(string &X, string &Y, int m, int n){// 动态规划表，大小(m+1)*(n+1)vector<vector<int>> table(m+1,vector<int>(n+1)); for(int i=0; i<m+1; ++i){for(int j=0; j<n+1; ++j){// 第一行和第一列置0if (i == 0 || j == 0)table[i][j] = 0;else if(X[i-1] == Y[j-1])table[i][j] = table[i-1][j-1] + 1;elsetable[i][j] = max(table[i-1][j], table[i][j-1]);}}return table[m][n];}int main(){string X = "ABCBDAB";string Y = "BDCABA";cout << "The length of LCS is " << lcs(X, Y, X.length(), Y.length());cout << endl;getchar();return 0;}

2. 连续子数组最大和

数组分析：下图是我们计算数组（1，-2，3，10，-4，7，2，-5）中子数组的最大和的过程。通过分析我们发现，累加的子数组和，如果大于零，那么我们继续累加就行；否则，则需要剔除原来的累加和重新开始。

过程如下：

class Solution {public:int FindGreatestSumOfSubArray(vector<int> array) {if(array.empty()){return 0;}// 初始化变量，maxSum为最大和，curSum为当前和int maxSum = array[0];int curSum = array[0];// 遍历所有元素for(int i = 1; i < array.size(); i++){// 如果当前和小于等于0，说明之前的是负数，则抛弃前面的和，重新计算if(curSum <= 0){curSum = array[i];}// 如果没有问题，直接累加else{curSum += array[i];}// 更新最大和if(curSum > maxSum){maxSum = curSum;}}return maxSum;}};

3. 最长递增子序列

对每一个 i，遍历 j（0 到 i-1）：

若A[i] <= A[j]，置 1。若A[i] > A[j]，取第 j 行的最大值加 1。

4. 最大递增子序列和

对每一个 i，遍历 j（0 到 i-1）：

若A[i] <= A[j]，置 A[i]。若A[i] > A[j]，取第 j 行满足A[i] > A[j]的最大值加 A[i]。

#include <iostream>#include <vector>#include <string>#include <algorithm>using namespace std;//最长上升子序列int main(){string str;getline(cin, str);vector<int> num;for (int i = 0; i < str.size(); ++i){if (str[i] != ' ')num.push_back(str[i] - '0');}int len = num.size();//最长上升子序列vector<int> dp(len, 0);for (int i = 0; i < len; ++i){int max_temp = 0;for (int j = 0; j < i; ++j){if (num[j] < num[i])max_temp = max(max_temp, dp[j]);}dp[i] = max_temp + 1;}//最大上升子序列和//vector<int> dp(len, 0);dp[0] = num[0];//很重要，5 1 3时最大是5，不加这一句最大就是1 3 = 4//for (int i = 0; i < len; ++i)//i从0开始//{//int max_temp = 0;//for (int j = 0; j < i; ++j)//{//if (num[j] < num[i])//max_temp = max(max_temp, dp[j]);//在满足num[j] < num[i]的基础上，////去找dp[j]中最大的存在max_temp中//}//dp[i] = max_temp + num[i];//}int max_res = 0;for (int i = 0; i < len; ++i)max_res = max(max_res, dp[i]);cout << max_res << endl;for (auto i : dp)cout << i;system("pause");return 0;}

miking time

描述

贝茜是一个勤劳的牛。事实上，她是那么专注于最大限度地提高了她的效率，她决定安排她的下ñ（1≤ñ≤1,000,000）小时（方便标记为0 ..ñ-1），使她产生尽可能多的牛奶越好。

农夫约翰的名单中号（1≤中号≤1000）可能是重叠的时间间隔，他可以挤奶其中。每个间隔我具有起动小时（0≤starting_hour我≤Ñ），结束小时（starting_hour我<ending_hour我≤Ñ），以及相应的效率（1≤效率我其指示的牛奶多少加仑≤1,000,000），他在那段时间里可以离开贝西。Farmer John分别在开始时间和结束时间开始时开始和停止挤奶。在挤奶时，Bessie必须在整个间隔内挤奶。

尽管贝茜有她的局限性。任何间隔期间挤奶后，她必须休息- [R（1≤[R≤Ñ）小时之前，她可以重新开始挤奶。鉴于Farmer Johns的间隔清单，确定Bessie在N小时内可以产生的最大牛奶量。

输入

*第1行：三个以空格分隔的整数：N，M和R

*第2行......M+1：第i+ 1行描述FJ的第i个挤奶间隔，其中包含三个以空格分隔的整数：starting_houri，ending_houri和效率i

产量

*第1行：Bessie在N小时内可以产生的最大加仑牛奶数

样本输入

12 4 21 2 810 12 193 6 247 10 31

样本输出

43

#include <iostream>#include <vector>#include <string>#include <algorithm>using namespace std;struct Nodes{int left;int right;int value;}node[1001];int cmp(Nodes a, Nodes b){return a.left < b.left;}int main(){int sum, n, r;cin >> sum >> n >> r;for (int i = 0; i < n; ++i)cin >> node[i].left >> node[i].right >> node[i].value;sort(node, node + n, cmp);vector<int> dp(n, 0);for (int i = 0; i < n; ++i){int max_temp = 0;for (int j = 0; j < i; ++j){if (node[j].right + r <= node[i].left)max_temp = max(max_temp, dp[j]);}dp[i] = max_temp + node[i].value;}cout << *max_element(dp.begin(), dp.end());system("pause");return 0;}