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

KaQqi

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

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

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

再定义一个数组去记录

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

然后先存数组里，再倒序打出，就变成正向了。
代码：

[Asm] 纯文本查看 复制代码

#include <stdio.h>

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

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

wushaominkk

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