记忆化搜索 警示后人
查看原帖
记忆化搜索 警示后人
616733
Lysea楼主2023/2/27 13:10

dp数组不能初设为0,因为当一个区间无法完全合并时值也为0。

比如以下代码,是无法AC的:

#include<bits/stdc++.h>
#define int long long
#define N 305
#define INF 0x3f3f3f3f
using namespace std;
int n,a[N],ans,dp[N][N];
int dfs(int l,int r){
	if(dp[l][r]) return dp[l][r];
	if(l==r) return dp[l][r]=a[l];
	for(int i=l;i<r;i++){
		if(dfs(l,i)==dfs(i+1,r)){
			dp[l][r]=max(dp[l][r],dp[l][i]+1);
			ans=max(ans,dp[l][i]+1);
		}
	}
	return dp[l][r];
}
signed main(){
	ios::sync_with_stdio(false);
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	dfs(1,n);
	cout<<ans;
    return 0;
}

2023/2/27 13:10
加载中...