rt，由于本人太蒻，不能直接想出状态转移方程，就先写了个爆搜的程序，然后把爆搜改装成了记忆化搜索

以下为记忆化搜索（只保留了核心部分）

long long dfs(long long d,long long change){
	if(d>n){
		return 0;
	}
	if(f[d][change]!=0){
		return f[d][change];
	}
	long long val=0;
	if(a[d]==d-change){
		val=max(val,dfs(d+1,change)+1);
	}else{
		val=max(val,dfs(d+1,change));
	}
	
	val=max(val,dfs(d+1,change+1));
	f[d][change]=val;
	return val;
}
	cout<<dfs(1,0);

然后TLE了，30分

我想了半天，感觉记忆化搜索推出的状态转移方程是正确的，于是我又写了一个DP

以下为DP（同样只有核心部分）

for(int i=1;i<=n;i++){
		for(int change=0;change<=i;change++){
			f[i][change]=max(f[i][change],f[i-1][change-1]);
			if(a[i]==i-change){
				f[i][change]=max(f[i][change],f[i-1][change]+1);
			}else{
				f[i][change]=max(f[i][change],f[i-1][change]);
			}
			ans=max(ans,f[i][change]);
		}
		
	}

这样可以A，100分

但是理论上~~（也有可能是我太蒻不知道）~~来说记忆化搜索和dp不是等价的吗，为什么记忆化会t而dp不会呢