关于最长上升子序列的疑惑(dp)
  • 板块学术版
  • 楼主Engulf
  • 当前回复2
  • 已保存回复2
  • 发布时间2021/8/16 22:38
  • 上次更新2023/11/4 10:24:43
查看原帖
关于最长上升子序列的疑惑(dp)
482728
Engulf楼主2021/8/16 22:38

最近在练dp,刷到了最长上升子序列,看了示例代码,其中有一处地方很是不解

for (int i = 2; i <= n; i++) {
	dp[i] = 1;
	for (int j = 1; j <= i - 1; j++) {
		if (a[j] <= a[i] && dp[j] + 1 > dp[i])dp[i] = dp[j] + 1;
		}
}

这里:

if(... && dp[j]+1 > dp[i])dp[i] = dp[j] + 1;

dp[j]+1>dp[i]的意义是什么?很是不解

还请个位大佬讲解一下!

2021/8/16 22:38
加载中...