最长上升子序列

用动态规划来解决最长上升子序列问题的需要注意：

问题是否有最优子结构性；无后效性：当前的若干个状态值一旦确定，则此后过程的演变就只和这若干个状态的值有关，和之前是采取哪种手段或经过哪种路径演变到当前的这若干个状态没有关系。

递归到动规的一般方法：递归函数有n个参数，就定义一个n维的数组，数组的下标是递归函数参数的取值范围，数组元素的值是递归函数的返回值，这样就可以从边界值开始，逐步填充数组，相当于计算递归函数值的逆过程。

---

在最长上升子序列问题中，假设序列为 a₁, a₂ …, a_k, …, a_n，想要通过动规的方式来求解，子问题是求以 a_k为终点的最长子序列，记为maxlen(k)，则求以 a_k+1为终点的最长子序列可以通过以 a₁, …, a_k中的点（该点的值小于 a_k）作为终点的最长子序列的最大值加上1求出来。因此问题具有最优子结构性。且在上述求解下一个状态值的过程中只与当前状态值有关，与如何到达当前状态无关，因此具有无后效性。 下面贴出通过建立备忘的递归方法以及直接递推求解问题的代码。

/*建立备忘的递归方法*/ #include <iostream> #include <algorithm> using namespace std; int maxlen(int); /* a1, a2, ..., ak, ..., an为一序列 以ak为终点的最长子序列即为maxlen(k) 递推公式： k!=1 => maxlen(k) = max{maxlen(i) && 1<=i<k && ai < ak} + 1; */ int N; int *MAXLEN; int *a; int main(void) { cin >> N; MAXLEN = (int *)malloc((N + 1) * sizeof(int)); if(MAXLEN == NULL){ cout << "error malloc space!" << endl; return -1; } a = (int *)malloc((N + 1) * sizeof(int)); if(a == NULL){ cout << "error malloc space" << endl; return -1; } for(int i = 1; i < N + 1; i++){ cin >> a[i]; MAXLEN[i] = -1; } int max = 0, len_i; for(int i = 1; i < N + 1; i++){ len_i = maxlen(i); if(len_i == 0){ MAXLEN[i] = 1; len_i = 1; } if(len_i > max) max = len_i; } cout << max << endl; return 0; } int maxlen(int k) { if(MAXLEN[k] != -1) return MAXLEN[k]; if(k == 1){ MAXLEN[k] = 1; return 1; } else{ int max = 0, tmp; for(int i = 1; i < k; i++){ if(a[i] < a[k]){ tmp = maxlen(i) + 1; if(tmp > max) max = tmp; } } MAXLEN[k] = max; return max; } }

---

/*直接递推求解*/ #include <iostream> #include <cstring> #include <algorithm> using namespace std; const int MAXN = 1010; int a[MAXN]; int maxlen[MAXN]; int main() { int N; cin >> N; for(int i = 1; i <= N; ++i){ cin >> a[i]; maxlen[i] = 1; } for(int i = 2; i <= N; ++i){ for(int j = 1; j < i; ++j) if(a[i] > a[j]) maxlen[i] = max(maxlen[i], maxlen[j]) + 1; } //max_element返回数组中最大的元素，左闭右开 cout << *max_element(maxlen + 1, maxlen + N + 1); return 0; }