动态规划刷题记录（2）

今天的三个题目属于模板题，可能将来会遇见它们的变形应用。

1、最长上升子序列问题

 这道题目的关键就在于我们的状态定义，我们定义：f(i)表示长度为i的子序列的末尾最大值。意思就是，比如一个子序列为：1,4,5，那么按我们的集合定义就应该是：f(3) = 5。这样定义了话我们就可以很容易的解题，我们只需要从头到尾遍历数组，找到当前数大于的最小值，然后更新找到的f。举个例子，f(2) = 3 f(3) = 5,这时候我们当前数是4,那么我们就把4接到3之后，也就是f(3) = 4。这里其实用到了贪心的思想，我们让不同长度的末尾值尽可能小，这样最长长度一定会尽可能长。代码你可以直接暴力寻找，也可以二分查找都可以。

#include <iostream>//直接暴力using namespace std;const int N = 1010;
int f[N] ,a[N] ,n;int main()
{cin >> n;for (int i = 1 ;i <= n ;i ++) cin >> a[i];for (int i = 1 ;i <= n ;i ++){f[i] = 1;for (int j = 1 ;j <= i ;j ++){if (a[i] > a[j]) f[i] = max(f[i] ,f[j] + 1);}}int res = -1;for (int i = 1 ;i <= n ;i ++) res = max(res ,f[i]);cout << res;return 0;
}

#include <iostream>//二分
#include <cstdio>
#include <algorithm>
#include <cstring>using namespace std;#define N 100100int f[N] ,len ,a[N] ,n;int main()
{cin >> n;for (int i = 1 ;i <= n ; i++) cin >> a[i];f[0] = -2e9;for (int i = 1 ;i <= n ;i ++){int l = 0 ,r = len;while (l < r){int mid = (l + r + 1) / 2;if (a[i] > f[mid]) l = mid;elser = mid - 1;}len = max(len ,r + 1);f[r + 1] = a[i];}cout << len;return 0;
}

2、最长公共子序列

这个题目的dp思路是：定义一个集合f(i ,j)表示字符串A的前i个字符以及字符串B的前j个字符中最长公共字符串长度。状态划分就可以是：1、a[i] == b[j]时，f[i][j] = f[i - 1][j - 1] +1。2、a[i] != b[j]时，最大公共字符串一定在A的前i - 1个字符和B的前j个字符 或者说A的前i个字符和B的前j - 1个字符中，因此，f[i][j] = max(f[i - 1][j] ,f[i][j - 1])。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>using namespace std;#define N 1100int f[N][N] ,n ,m;
char a[N] ,b[N];int main()
{cin >> n >>m;scanf("%s" ,a + 1);scanf("%s" ,b + 1);f[0][0] = 0;for (int i = 1 ;i <= n ;i ++)for (int j = 1 ;j <= m ;j ++){if (a[i] == b[j]) f[i][j] = f[i - 1][j - 1] + 1;f[i][j] = max(f[i - 1][j] ,f[i][j]);f[i][j] = max(f[i][j - 1] ,f[i][j]);}cout << f[n][m];return 0;
}

3、最长公共上升子序列

 这道题的思路是前两道题的结合版本，更加的复杂，很难想到。f(i ,j)表示第一个序列前i个字母以及第二个序列前j个字母，并且以b[j]结尾的公共上升子序列的最大值。那么我们的状态划分就可以分为两大类：一、a[i] ！= b[j]的时候，最大公共上升序列跟a[i]无关，那么状态转移:f[i][j] = f[i - 1][j]。二、a[i] == b[j]的时候，最大公共上升序列的末尾就是a[i] ,那么我们就根据倒数第二个值是哪一个划分状态，f[i][j] = max(f[i - 1][1] ,f[i - 1][2] .......f[i - 1][j - 1])。根据这个思路我们写出代码：

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>using namespace std;#define N 3500
#define ll long longll f[N][N] ,n ,a[N] ,b[N];int main()
{cin >> n;for (int i = 1 ;i <= n ;i ++) cin >> a[i];for (int j = 1 ;j <= n ;j ++) cin >> b[j];for (int i = 1 ;i <= n ;i ++){for (int j = 1 ;j <= n ;j ++){ll maxv = 1;//作为中间值存取f(i - 1 ,1 ~ j - 1)的最大值f[i][j] = f[i - 1][j];if (a[i] == b[j]){for (int k = 1 ;k < j ;k ++){if (a[i] > b[k]) maxv = max(maxv ,f[i - 1][k] + 1);//注意，必须a[i] > b[k]否则就不能满足递增序列的条件。}f[i][j] = max(f[i][j] ,maxv);}}}ll ans = -1e9;for (int i = 1 ;i <= n ; i ++) ans = max(ans ,f[n][i]);cout << ans;return 0;
}

 三重循环n方复杂度，很明显时间复杂度太高，我们考虑优化。根据代码我们可以看出，在i确定的情况下，f[i][k - 1]的值是跟j没有关系的，我们就可以优化掉第三层循环：

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>using namespace std;#define N 3050int f[N][N] ,n ,a[N] ,b[N];int main()
{cin >> n;for (int i = 1 ;i <= n ;i ++) cin >> a[i];for (int j = 1 ;j <= n ;j ++) cin >> b[j];for (int i = 1 ;i <= n ;i ++){int maxv = 1;for (int j = 1 ;j <= n ;j ++){f[i][j] = f[i - 1][j];if (a[i] == b[j]) f[i][j] = max(f[i][j] ,maxv);if (a[i] > b[j])  maxv = max(maxv ,f[i - 1][j] + 1);}}int ans = 0;for (int i = 1 ;i <= n ; i ++) ans = max(ans ,f[n][i]);cout << ans;return 0;
}