我的邏輯最小硬幣需要

Question

我試圖自己做錢幣改變的問題，但它看起來像我的邏輯是缺乏的地方，請幫助我。我已經評論了我的想法。

#include <bits/stdc++.h> 
using namespace std; 
vector<int>nom; 

int dp[1000004]; 

int recurse(int v){ 

    if(dp[v]!=-1)return dp[v];  // If already found something just return 
    if(v==0)return 0;  // If value is 0.Minimum changes req is 0. 
    if(v<0)return INT_MAX; // If reached out of bound return MAX. 
    int ans=INT_MAX;   // For storing Ans. 

    for(int i=0;i<nom.size();i++){ 
    ans=min(ans,recurse(v-nom[i])+1); //Min Number of changes req fir val-nom[i]+1 for value val. 
    } 
dp[v]=ans; 
return dp[v]; 
} 

int main() { 
    int v,n,x; 
    cin>>v>>n;  // Value for which I have to find change,No. of change available 

    for(int i=0;i<n;i++){ 
    cin>>x; 
    nom.push_back(x); // changes 
    dp[x]=1;  // If we want x money only 1 change req so dp[x]=1 
    } 

    int mincoins=0;  // For storing answer 
    mincoins=recurse(v); // Answer for value v. 
    cout<<mincoins<<endl; 
    } 
    return 0; 
} 

Answer 1

這裏唯一的問題是，你忘了的dp[]所有元素初始化爲-1。