硬币

题目大意

分析

贪心的从大到小面值去取硬币

然后每次可以产生两种情况

1. 取 $sum/a[i]$个剩下的用后面的硬币去补
2. 取 $(sum/a[i])+1$ 个多的减去后面的硬币

记忆化搜索

理论上会有很多情况复杂度可能会很大

不过发现对每一层会有很多重复的 sum

Code

int n,x;
map<int,map<int,int>> f;
int a[65];
int dfs(int sum,int i){
     if(i == 1) return sum;
     if(f[sum][i]) return f[sum][i];
     if(sum % a[i] == 0) return sum / a[i];
     int w1 = sum/a[i] + dfs(sum%a[i],i-1);
     int w2 = 1 + sum/a[i] + dfs((sum/a[i]+1)*a[i] - sum,i-1);
     return f[sum][i] = min(w1,w2); 
}  
signed main()
{
    cin >> n >> x;
    for(int i = 1;i <= n;i++) cin >> a[i];
    cout << dfs(x,n) << endl;
    return 0;
}