动态规划——零钱兑换（python）

思路dp[i]定义为求能够凑成数i所需要的最少个数为dp[i]。状态转移dp[i]min(dp[i-coins[i]]1,dp[i]。这里是求个数求个数求个数所以这里是由上个状态加数字1转移这里要好好理解。def coinsChange(coins,n): #求能凑成i的最少个数 dp[float(inf)]*(n1) dp[0]0 for i in range(1,n1): for j in coins: if ij: dp[i]min(dp[i-j]1,dp[i]) if dp[n]float(inf): return -1 return dp[n] def main(): coinslist(map(int,input().split())) nint(input()) rescoinsChange(coins,n) print(res) if __name____main__: main()