【动态规划专题】LeetCode 322. 零钱兑换

本问题对应课程链接：剑指offer刷题第三期

要求：
1、请打卡你的解题代码，如果能简单说一下思路则简单说一下思路。
2、给出你代码所用的时间复杂度和空间复杂度

shuaidi

更新于 3 年前 128 10

共以下 10 个回答

招舟子普通 2024年1月3日下午7:45

public class Solution {
public int coinChange(int[] coins, int amount) {
int max = amount + 1;
int[] dp = new int[amount + 1];
Arrays.fill(dp, max);
dp[0] = 0;
for (int i = 1; i <= amount; i++) {
for (int j = 0; j < coins.length; j++) {
if (coins[j] <= i) {
dp[i] = Math.min(dp[i], dp[i – coins[j]] + 1);
}
}
}
return dp[amount] > amount ? -1 : dp[amount];
}
}
动态规划

0 赞同 0 条回复

登录以回复

mpweixin用户永久会员 2023年7月25日上午11:53

class Solution {
    public int coinChange(int[] coins, int amount) {

        int max = amount + 1;
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, max);
        dp[0] = 0;  //组成0，不需要硬币

        for (int i = 1; i <= amount; i++) {
            for (int j = 0; j < coins.length; j++) {
                //遍历各种面值
                if (coins[j] <= i) {
                    dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);
                }
            }
        }
        return dp[amount] > amount ? -1 : dp[amount];
    }

}

0 赞同 0 条回复

张开怀普通 2023年7月24日下午7:51

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        int Max = amount + 1;
        vector<int> dp(amount + 1, Max);
        dp[0] = 0;
        for (int i = 1; i <= amount; ++i) {
            for (int j = 0; j < (int)coins.size(); ++j) {
                if (coins[j] <= i) {
                    dp[i] = min(dp[i], dp[i - coins[j]] + 1);
                }
            }
        }
        return dp[amount] > amount ? -1 : dp[amount];
    }
};

时间复杂度：O(sn) s是总金额，n是面额数
空间复杂度：O(s)

0 赞同 0 条回复

Dsjh 普通 2023年7月24日上午11:29

MY

// 这是中文
class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        if(amount==0){
            return 0;
        }
        int Max = amount+1;
        vector<int> dp(amount+1,Max);
        dp[0] = 0;
        for(int i=1;i<=amount;i++){
            for(int j=0;j<coins.size();j++){
                if(coins[j]<=i){
                    dp[i] = min(dp[i],dp[i-coins[j]]+1);
                }
            }
        }
        return dp[amount] > amount ? -1 : dp[amount];

    }
};

0 赞同 0 条回复

花老爷普通 2023年7月23日下午4:56

动态规划
时间：O(mn)
空间：O(n)

class Solution {
    public int coinChange(int[] coins, int amount) {
        if (amount == 0) {
            return 0;
        }
        int[] dp = new int[amount + 1];
        for (int i = 1; i <= amount; i++) {
            for (int j = 0; j < coins.length; j++) {
                if (i == coins[j]) {
                    dp[i] = 1;
                } else if (i - coins[j] >= 0 && dp[i - coins[j]] > 0) {
                    dp[i] = dp[i] == 0 ? dp[i - coins[j]] + 1 : Math.min(dp[i], dp[i - coins[j]] + 1);
                }
            }
        }
        return dp[amount] == 0 ? -1 : dp[amount];
    }
}

0 赞同 0 条回复

怀瑾永久会员 2023年7月23日下午3:54

C++实现

“`C++
class Solution {
public:
int coinChange(vector& coins, int amount) {
vector dp(amount+1, INT_MAX);
dp[0] = 0;
for(int j=1;j<=amount;j++) { for(auto coin: coins) { if(j-coin>=0&&dp[j-coin]!=INT_MAX)
dp[j]=min(dp[j], dp[j-coin]+1);
}
}
if(dp[amount]==INT_MAX)
return -1;
return dp[amount];
}
};
“`

0 赞同 0 条回复

登录以回复

Vow the vow。普通 2023年7月23日下午12:32

时间复杂度：O(n * amount)

public int coinChange(int[] coins, int amount) {
        int n = coins.length; 
        int[][] f = new int[n+1][amount+1];
        for(int i = 0; i <= n; i++){
            Arrays.fill(f[i],Integer.MAX_VALUE/2);
        }
        f[0][0] = 0;
        for(int i = 0; i < n; i++){
            for(int c = 0; c <= amount; c++){
                if(c < coins[i]) f[i+1][c] = f[i][c];
                else f[i+1][c] = Math.min(f[i][c], f[i+1][c-coins[i]]+1);
            }
        }
        return f[n][amount] < Integer.MAX_VALUE/2 ? f[n][amount] : -1;
    }

0 赞同 0 条回复

哈哈哈哈开开心心普通 2023年7月23日上午5:25

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:

        dp = [-1] * (amount + 1)
        dp[0] = 0

        for i in range(len(coins)):
            for j in range(coins[i], amount + 1):
                if dp[j - coins[i]] == -1:
                    continue
                elif dp[j] == -1:
                    dp[j] = dp[j - coins[i]] + 1
                else:
                    dp[j] = min(dp[j], dp[j - coins[i]] + 1)
        return dp[amount]

动态规划

0 赞同 0 条回复

yxy 普通 2023年7月22日下午5:52

时间复杂度O(n)

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        vector<int> dp(amount+1, INT_MAX);
        dp[0] = 0;
        for(int j=1;j<=amount;j++)
        {
            for(auto coin: coins)
            {
                if(j-coin>=0&&dp[j-coin]!=INT_MAX)
                    dp[j]=min(dp[j], dp[j-coin]+1);
            }
        }
        if(dp[amount]==INT_MAX)
            return -1;
        return dp[amount];
    }
};

0 赞同 0 条回复

Yodl. 普通 2023年7月22日下午5:51

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        int Max = amount + 1;
        vector<int> dp(amount + 1, Max);
        dp[0] = 0;
        for(int i=1;i<=amount;i++)
        {
            for(int j=0;j<coins.size();j++)
            {
                if(coins[j]<=i)
                {
                    dp[i]=min(dp[i],dp[i-coins[j]]+1);//状态转移方程：dp[i]=min(dp[amount-coins[0]],dp[amount-coins[1]],dp[amount-coins[2]],...);
                }
            }
        }
        return dp[amount]>amount?-1:dp[amount];
    }
};

0 赞同 0 条回复

# 回答此问题取消回复

后才能回答

【动态规划专题】LeetCode 322. 零钱兑换

共以下 10 个回答

MY

# 回答此问题 取消回复

# 回答此问题取消回复