如何为最小硬币问题记住这种重复？

Question

我试着记住 'x' 的值，但它给出了错误的答案。

取消评论部分的评论会给出错误的答案。

//vi dp(1000001,-1);

int f(int x,int cnt,const vi &v){
    if(x<0)return INT_MAX;
    if(x==0)return cnt;
    //if(dp[x]!=-1)return dp[x];
    int ans=INT_MAX;
    for(const int &i:v){
        ans=min(ans,f(x-i,cnt+1,v));
    }
    //dp[x]=ans;
    return ans;
}

没有记忆，这工作正常。

Answer 1

您的函数有 2 个状态，而您只存储一个状态的值。假设您需要 f(2,2,v) 的值。您的 dp[2] 数组可以包含 f(2,x,v) 中的任何值，其中 x 可以是 "cnt" 的任何值。