C/C++教程

Coin Change（C++零钱兑换）

本文主要是介绍Coin Change（C++零钱兑换），对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！


（1）dp，完全平方数类似

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        int maxs=amount+1;
        int n=coins.size();

        vector<int> v(amount+1,maxs);
        v[0]=0;
        for(int i=1;i<amount+1;i++) {
            for(int j=0;j<n;j++) {
                if(i>=coins[j])
                v[i]=min(v[i],v[i-coins[j]]+1);
            }
        }
        return v[amount]==maxs?-1:v[amount];
    }
};

这篇关于Coin Change（C++零钱兑换）的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
您可能喜欢
栏目导航