题解 | #Redraiment的走法#
Redraiment的走法
https://www.nowcoder.com/practice/24e6243b9f0446b081b1d6d32f2aa3aa
最近在学动态规划，受到动态规划的启发
定义状态数组dp[n]，表示从下标i开始走最多有dp[i]种走法
注意要从后到前开始遍历
#include <stdio.h>
int main()
{
int n;
scanf("%d",&n);
int a[n],i,j;
for(i=0;i<n;i++) scanf("%d",&a[i]);
int dp[n]; //从下标为n走最多有dp[n]种走法
for(i=0;i<n;i++) dp[i]=1;//初始化赋值为1，算自身的一步
for(i=n-2;i>=0;i--)//从后向前遍历
for(j=i+1;j<n;j++)
if(a[i]<a[j])
if(dp[i]<1+dp[j]) dp[i]=1+dp[j];
int max=0;
for(i=0;i<n;i++)
if(max<dp[i]) max=dp[i];
printf("%d",max);
return 0;
}