动态规划-最长单调递增子序列(dp)

解题思想：动态规划

1.解法1(n2)

　状态：d[i] = 长度为i+1的递增子序列的长度

　状态转移方程：dp[i] = max(dp[j]+1, dp[i]);

分析：最开始把dp数组初始化为1，然后从前往后考虑数列的元素，对于每个aj，如果a[i] > a[j]，就用dp[i] = max(dp[i], dp[j] + 1)进行更新，再从dp数组中找出最大值即为结果

举例：abklmncdefg

　　　 dp[0] = 1; dp[1] = 2; dp[2] = 3; dp[3] = 4; dp[4] = 5; dp[5] = 6; dp[7] = 3; dp[8] = 4; dp[9] = 5; dp[10] = 6; dp[11] = 7; 最大值为7

　代码：

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 using namespace std;
 5 const int MAX_N = 10005;
 6 int n;
 7 char a[MAX_N];
 8 int dp[MAX_N];
 9 int main() {
10     int n;
11     cin >> n;
12     while(n--) {
13         int ans = 0;
14         fill(dp, dp+MAX_N, 1);
15         cin >> a;
16         int len = strlen(a);
17         for(int i = 0; i < len; i++) {
18             for(int j = 0; j < i; j++) {
19                 if(a[j] < a[i]) dp[i] = max(dp[i], dp[j] + 1);
20             }
21             ans = max(ans, dp[i]);
22         }
23         cout << ans << endl;
24     }
25     return 0;
26 }

View Code

2.解法2(n2)

　状态：d[i] = 长度为i+1的递增子序列中末尾的最小值(不存在就是INF)

　分析：最开始用INF初始化dp数组的值，然后从前往后考虑数列的元素，对于每个aj，如果i = 0或者a[j] >= a[i]，使得a[j] = a[i]并且break出来，最后第一个dp数组中值为INF的下标即为结果

　举例：abklmncdefg

　　　 a; ab; abk; abkl; abklm; abklmn; abclmn; abcdmn; abcden; abcdef; abcdefg; 第一个INF的下标为7　

　代码：

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 using namespace std;
 5 const int MAX_N = 10005;
 6 const int INF = 127;
 7 int n;
 8 char a[MAX_N];
 9 char dp[MAX_N];
10 int main() {
11     int n;
12     cin >> n;
13     while(n--) {
14         fill(dp, dp+MAX_N, INF);
15         cin >> a;
16         int len = strlen(a);
17         for(int i = 0; i < len; i++) {
18             for(int j = 0; j < len; j++) {
19                 if(!i || dp[j] >= a[i])  {
20                     dp[j] = a[i]; break;
21                 }
22             }
23         }
24         int ans = 0;
25         while(dp[ans] != INF) ans++;
26         cout << ans << endl;
27     }
28     return 0;
29 }

View Code

3.解法3(nlogn)

　分析：思路与解法2一样，但是解法2可以进一步优化，在解法2中dp数组是单调递增的，每次要从头到尾找到第一个大于等于a[i]的值，这是o(n2)的，既然是顺序的可以使用二分查找进行改进，

　　　　这样可以在o(nlogn)时间内求出结果，这里利用到了STL中的lower_bound(dp, dp + n, a[i])，找出dp数组中大于等于a[i]的最小的指针，upper_boundlower_bound(dp, dp + n, a[i])，找出dp数组中大于a[i]的最大的指针

代码：

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 using namespace std;
 6 const int MAX_N = 10005;
 7 const int INF = 127;
 8 int n;
 9 char a[MAX_N];
10 char dp[MAX_N];
11 int main() {
12     int n;
13     cin >> n;
14     while(n--) {
15         fill(dp, dp+MAX_N, INF);
16         cin >> a;
17         int len = strlen(a);
18         for(int i = 0; i < len; i++) {
19             *lower_bound(dp, dp+len, a[i]) = a[i];
20         }
21         cout << lower_bound(dp, dp+len, INF) - dp << endl;
22     }
23     return 0;
24 }

View Code

动态规划-最长单调递增子序列(dp)

推荐阅读