Как запомнить это повторение для минимальной проблемы с монетами?

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».