零钱兑换
题目链接: https://leetcode.cn/problems/coin-change/
解题思路:
设定一维数组dp,dp[i]代表金额为i的时候所需要的最小硬币个数
dp[i]=min(dp[i-coins[j]])+1
最大值选择math.MaxInt会有超int问题,故再次max选择amount+1
复杂度分析
时间复杂度: 时间复杂度是 其中 是数组
coins
的数量,也就是不同面额的硬币的数量空间复杂度: 空间复杂度是
最后更新于
题目链接: https://leetcode.cn/problems/coin-change/
设定一维数组dp,dp[i]代表金额为i的时候所需要的最小硬币个数
dp[i]=min(dp[i-coins[j]])+1
最大值选择math.MaxInt会有超int问题,故再次max选择amount+1
时间复杂度: 时间复杂度是 其中 是数组 coins
的数量,也就是不同面额的硬币的数量
空间复杂度: 空间复杂度是
最后更新于