algorithm - 我需要的最低硬币逻辑

Question

我正在尝试自己解决 Coin Change 问题。但似乎我的逻辑缺乏某些地方，请帮助我。我已经评论了我的想法。

#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。