题目描述

我的思路 & 求助

一道 DP 题目（显然是的），我考虑 $f_{i,j}f i,j$表示最后一个染黑和倒数第二个的分别是 $j$ 和 $i$。转移方程是 $f_{i,j}=\min_{j-m\le k \le i-1}(f_{k,i}+c_j)$。但是 $O(n^2)$的空间复杂度肯定会爆掉，所以考虑优化成 $O(n * m)$ 的空间，用 $f_{i,j}$ 表示最后一个染黑的是第 $i+j$ 个,倒数第二个被染黑的是第 $i$ 个。同时优化时间复杂度，倒序枚举 $j$，这样查找最小值就可以在 $O(1)$ 内完成。但现在问题在于一直答案错误 60pts，我把代码发上来求教，有没有大佬指点一下？（ps：网上有空间复杂度 $O(m^2)$ 的题解，但是那对我来说太玄学了，基本搞不懂，如果有大佬能够解释一下那种写法就更好了）

#include<bits/stdc++.h>
#define MAXN 20010
#define MAXM 2010
#define INF 2000000000
using namespace std;
int n,m;
/*
    dp[i][j] -> 最后一个染黑的是第 i+j 个,倒数第二个被染黑的是第 i 个
*/
int dp[MAXN][MAXM],cost[MAXN];
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%d",&cost[i]),dp[0][i]=cost[i];
    for(int i=1;i<=n;i++){
        int minn=INF;
        for(int j=min(i+m-1,n);j>i;j--){
        	minn=min(minn,dp[max(j-m,0)][i-max(j-m,0)]);
            dp[i][j-i]=cost[j]+minn;
        }
    }
    int ans=INF;
    for(int i=n-m;i<n;i++){
        for(int j=i+1;j<=n&&j<i+m;j++){
            ans=min(ans,dp[i][j-i]);
        }
    }
    printf("%d\n",ans);
    return 0;
}