提交：/problem/1048/
递推
//f[i]:到i为止的LIS的长度。//f[i]=max{1,f[j]+1|j<i&&aj<ai}#include<iostream>#include<algorithm>using namespace std;int n, a[510], f[510], ans;int main(){cin>>n;for(int i = 1; i <= n; i++)cin>>a[i];for(int i = 1; i <= n; i++){int t = 0;for(int j = 1; j < i; j++)if(a[j]<a[i])t = max(t, f[j]);f[i] = t+1;ans = max(ans, f[i]);}cout<<ans<<"\n";return 0;}
递归
#include<iostream>#include<algorithm>using namespace std;const int maxn = 1010, inf=0xffffff;int w[maxn], f[maxn][maxn];int dp(int i, int j){if(f[i][j] != inf)return f[i][j];for(int k = i; k <= j; k++)f[i][j] = min(f[i][j], dp(i,k)+dp(k+1,j)+w[j]-w[i-1]);return f[i][j];}int main(){int n; cin>>n;for(int i = 1; i <= n; i++)cin>>w[i];for(int i = 1; i <= n; i++)for(int j = 1; j <= n; j++)f[i][j] = i==j ? 0 : inf;for(int i = 1; i <= n; i++)w[i] += w[i-1];cout<<dp(1,n)<<"\n";return 0;}
