对于DP为何要取max正确

我们知道每次区间DP更新时，由于这个DP区间只能被遍历一次，并且他被更新时合并成的数是唯一的。所以应该不用区max但但但提交后错了。就像这样

CPP

#include <bits/stdc++.h>
using namespace std;
int n,a[250],dp[250][250],ans;
signed main(){
	cin>>n;
	memset(dp,-0x3f,sizeof(dp));
	for(int i=1;i<=n;i++){
		cin>>a[i];
		dp[i][i]=a[i];
		ans=max(ans,a[i]);
	}
	for(int l=2;l<=n;l++){
		int g=n+1-l;
		for(int i=1;i<=g;i++){
			int gg=i+l-1;
			for(int k=i;k<gg;k++){
				if(dp[i][k]==dp[k+1][gg]){
					dp[i][gg]=dp[i][k]+1;//没有取max
					ans=max(ans,dp[i][gg]);
				}
			}
		}
	}
	cout<<ans;
	return 0;
}

首先我们知道DP需要初始化为极小值（-0x3f3f3f3f）因为如果两个都没有被遍历的DP值为0，此时两个DP合并后为1，这样就会出错。

但当你发现就算你初始化为极小值（-0x3f3f3f3f）它这两个小区间DP还是会合并的，虽然值小不会存ans，但它会因赋值，顶掉之前被赋过正确值的大区间DP

这样原本应该是正数的大DP区间变成了极小值（-0x3f3f3f3f）+1。所以如果加上判定：当小区间大于0则不更新时就不需要加max：

CPP

#include <bits/stdc++.h>
using namespace std;
int n,a[250],dp[250][250],ans;
signed main(){
	cin>>n;
	//memset(dp,-0x3f,sizeof(dp));
	for(int i=1;i<=n;i++){
		cin>>a[i];
		dp[i][i]=a[i];
		ans=max(ans,a[i]);
	}
	for(int l=2;l<=n;l++){
		int g=n+1-l;
		for(int i=1;i<=g;i++){
			int gg=i+l-1;
			for(int k=i;k<gg;k++){
				if(dp[i][k]==dp[k+1][gg]&&dp[i][k]>0){
					dp[i][gg]=dp[i][k]+1;//不需加max
					ans=max(ans,dp[i][gg]);
				}
			}
		}
	}
	cout<<ans;
	return 0;
}

讨论区某人疑问：dp[l][r]存储max，后续在更新时用dp[l][r]更新（即[l,r]的max）是否不妥？会不会出现不用max（比max小时的dp[l][r]）才能更新，且全部更新完后新的max比(dp[l][r])max更大的情况。

解释：不会，因为dp[l][r]里存的是固定的，它是在[l,r]区间合并后产生的唯一的一个数而其他情况下它的值都是因为错误转移而来的（即上文提到的两个未被赋值的DP合成来的）。

对于DP为何要取max正确

讨论操作

回复

相关推荐

对于DP为何要取max正确