题解 | #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;
}