题解 | #Redraiment的走法#
Redraiment的走法
https://www.nowcoder.com/practice/24e6243b9f0446b081b1d6d32f2aa3aa
本题有两种解法
解法一是使用递归解法，缺点是运行时间长，有大量重复计算，解法2是动态规划解法
//解法1：递归解法
#include<stdio.h>
#include<string.h>
int num;
int high[200];
int find(int i)
{
int step = 1;
if (i == num - 1) { return 1; }
else
{
for (int j = i + 1; j < num; j++)
{
if (high[j] > high[i])
{
step = (step > (find(j) + 1)) ? step : (find(j) + 1);
}
}
}
return step;
}
int main(void)
{
scanf("%d", &num);
for (int i = 0; i < num; i++)
{
scanf("%d", &high[i]);
}
int max = 1;
for (int i = 0; i < num; i++)
{
max = (max > find(i)) ? max : find(i);
}
printf("%d", max);
return 0;
}
解法2是优化后的动态规划解法，增加了缓存数组，但本质上还是基于递归法
//解法2：动态规划解法
//主旨是定义缓存数组，减少重复计算
#include<stdio.h>
#include<string.h>
int num;
int high[200];
int dp[200]={0};
int find(int i)
{
int step=1;
if(dp[i]!=0){return dp[i];}//如果dp数组中已经缓存了之前存储的数据，则不用再进行计算
if(i==num-1){return 1;}
else
{
for(int j=i+1;j<num;j++)
{
if(high[j]>high[i])
{
step=(step>(find(j)+1))?step:(find(j)+1);
dp[i]=step;
}
}
}
return step;
}
int main(void)
{
scanf("%d",&num);
for(int i=0;i<num;i++)
{
scanf("%d",&high[i]);
}
int max=1;
for(int i=0;i<num;i++)
{
max=(max>find(i))?max:find(i);
}
printf("%d",max);
return 0;
}
解法3是利用迭代法的动态规划方法，运行时间大量减少
//解法2：动态规划解法
//主旨是定义缓存数组，减少重复计算
#include<stdio.h>
#include<string.h>
int num;
int high[200];
int dp[200] = { 0 };
int main(void)
{
scanf("%d", &num);
for (int i = 0; i < num; i++)
{
scanf("%d", &high[i]);
}
//倒着遍历
for (int i = 0; i < num; i++) { dp[i] = 1; }
for (int i = num - 1; i >= 0; i--)
{
for (int j = i + 1; j < num; j++)
{
if (high[j] > high[i])
{
dp[i] = (dp[i] > dp[j] + 1) ? dp[i] : dp[j] + 1;
}
}
}
int max = 1;
for (int i = 0; i < num; i++)
{
max = (max > dp[i]) ? max : dp[i];
}
printf("%d", max);
return 0;
}
