669. Coin Change

Code(Language:C++) (Judger:cloudjudge-cluster-4)

class Solution {
public:
    /**
     * @param coins: a list of integer
     * @param amount: a total amount of money amount
     * @return: the fewest number of coins that you need to make up
     */
    int coinChange(vector<int> &coins, int amount) {
        // write your code here
        const int n = coins.size();
        if(amount == 0){
            return 0; 
        }
        if(n <= 0){
            return -1; 
        }
        vector<vector<int>> dp(amount + 1, vector<int>(n + 1, amount + 1)); 
        dp[0][0] = 0; 
        
        for(int i = 1; i <= amount; i++){
            for(int j = 1; j <= n; j++){
                dp[0][j] = 0; 
                if(coins[j - 1] <= i){
                    dp[i][j] = min(dp[i - coins[j - 1]][j] + 1, dp[i][j - 1]); 
                }
                else{
                    dp[i][j] = dp[i][j - 1]; 
                }
            }
        }
        return dp[amount][n] == amount + 1? -1 : dp[amount][n]; 
    }
};