网站 › 『编程语言区』 › 动态规划时实现记录最优解

KaQqi 发表于 2019-4-20 10:17

动态规划时实现记录最优解

题目：http://ybt.ssoier.cn:8088/problem_show.php?pid=1259

思路1：通过记忆化递归模式dp（太简单了，不说了）
思路2：从dp过程状态转移的实际含义去实现

这个dp的含义就是当前位置的最长不下降序列的长度
所以就记录当前位置的上一个位置是多少

再定义一个数组去记录

但是这样貌似只能倒着打出来

然后先存数组里，再倒序打出，就变成正向了。
代码：
#include <stdio.h>

int data;
int dp;
int last;
int result;
int main()
{
        int n;
       
        scanf("%d",&n);
        for(int i = 0;i<n;i++)
        {
                scanf("%d",&data);
        }
        dp = 1;
        for(int i = 0;i<n;i++)
        {
                for(int j = 0;j<i;j++)
                {
                        if(data <= data)
                        {
                                if(dp + 1 > dp) dp = dp+1;
                                last = j;
                        }
                }
        }

       
       
        int max = 0;
        int max_pos;
        for(int i = 0;i<n;i++)
        {
                if(dp > max)
                {
                       max=dp;
                       max_pos = i;
                }
        }
        printf("max=%d\n",max+1);
        int print = max_pos;
        for(int i = 0;i<=max;i++)
        {
                result = data;
                print = last;
        }
        for(int i = max;i>=0;i--) printf("%d ",result);
}

wushaominkk 发表于 2019-4-20 19:58

感谢您坚持发帖，吾爱因您更精彩！

查看完整版本: 动态规划时实现记录最优解