换一个可以填表的动态规划
时间: 2023-07-08 15:35:17 浏览: 33
这是一个使用动态规划算法解决最长上升子序列问题的例题:
```cpp
#include <iostream>
#include <algorithm>
using namespace std;
const int MAXN = 100;
int n;
int a[MAXN], dp[MAXN]; // a 存储序列,dp[i] 表示以 a[i] 结尾的最长上升子序列的长度
int main() {
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
for (int i = 1; i <= n; i++) {
dp[i] = 1; // 初始化,每个元素自成一个长度为 1 的上升子序列
for (int j = 1; j < i; j++) {
if (a[i] > a[j]) { // a[i] 可以接在 a[j] 后面形成更长的上升子序列
dp[i] = max(dp[i], dp[j] + 1);
}
}
}
int ans = 0;
for (int i = 1; i <= n; i++) {
ans = max(ans, dp[i]); // 找到最长的上升子序列的长度
}
cout << ans << endl;
return 0;
}
```
代码中使用了一个一维数组 `dp`,其中 `dp[i]` 表示以 a[i] 结尾的最长上升子序列的长度。对于每个 a[i],初始化 `dp[i]=1`,表示它自成一个长度为 1 的上升子序列。然后,对于每个 j<i,如果 a[i] 可以接在 a[j] 后面形成更长的上升子序列,则更新 `dp[i]=max(dp[i], dp[j]+1)`。最终,遍历 `dp` 数组找到最大的元素即为最长上升子序列的长度。