DP最少硬币

#include<bits/stdc++.h> using namespace std; int coinChange(int A[],int n,int m) { int *f=new int[m+1]; f[0]=0;//应付的钱为0时，最少的硬币数 int i,j; for(i=1;i<=m;i++) { f[i]=INT_MAX;//初始化为无穷大 //f[i]=min{f[i-A[0]]+1,f[i-A[1]]+1,...,f[i-A[n-1]]+1} for(j=0;j<n;j++) { if(i>=A[j]&&f[i-A[j]]!=INT_MAX)//应付的硬币数量应该大于硬币的面值且按照这样付钱可以付够 { f[i]=min(f[i-A[j]]+1,f[i]); } } } if(f[m]==INT_MAX) { f[m]=-1; } return f[m]; } int main() { int n,m;//n是硬币的种类数，m是应该付的钱数 cin>>n>>m; int*a=new int[n]; for(int i=0;i<n;i++) { cin>>a[i]; } cout<<coinChange(a,n,m); return 0; }