C++ 解法, 执行用时: 3ms, 内存消耗: 428KB, 提交时间: 2021-09-09

class Exchange {
public:
    int countWays(vector<int> changes, int n, int x) {
        vector<int> dp(x+1, 0);
        dp[0] = 1;
        for(const auto &coin: changes){
            for(int i = coin; i<=x; ++i){
                dp[i] += dp[i-coin];
            }
        }
        return dp[x];
    }
};

C++ 解法, 执行用时: 4ms, 内存消耗: 424KB, 提交时间: 2021-11-22

class Exchange {
public:
    int countWays(vector<int> changes, int n, int x) {
        // write code here
        vector<int> dp(x+1);
        dp[0]=1;
        sort(changes.begin(), changes.end());
        for(int coin:changes)
        {
            for(int i=coin; i<=x; i++)
            {
                dp[i]+=dp[i-coin];
            }
        }
        return dp[x];
    }
};

C++ 解法, 执行用时: 4ms, 内存消耗: 432KB, 提交时间: 2021-09-07

class Exchange {
public:
    int countWays(vector<int> changes, int n, int x) {
        vector<int> dp(x+1,0);
        dp[0] = 1;
        for(int j = 0;j<n;j++)
        {
            for( int i = changes[j];i<=x;i++)
            {
                dp[i]+=dp[i-changes[j]];
            }
        }
        return dp[x];
    }
};

C++ 解法, 执行用时: 4ms, 内存消耗: 440KB, 提交时间: 2022-05-19

class Exchange {
public:
    int countWays(vector<int> changes, int n, int x) {
        // write code here
                // 初始化
        vector<int> dp(x+1, 0);
        dp[0] = 1;
        //动态规划
        for(int i=0; i<n; i++){
            int value = changes[i];
            for(int j=value; j<=x; j++){
                //将max改为为sum
                dp[j] = dp[j] + dp[j-value];
            }
        }
        return dp[x];
    }
};

C++ 解法, 执行用时: 4ms, 内存消耗: 448KB, 提交时间: 2021-12-11

class Exchange {
public:
    int countWays(vector<int> changes, int n, int x) {
        // write code here
        vector<int> dp(x+1);
        dp[0] = 1;
        for(int i = 0; i < changes.size(); ++i) {
            for(int j =0; j + changes[i] < x+1; ++j) {
                dp[j+changes[i]] += dp[j];
            }
        }
        return dp[x];
    }
};