动态规划——零钱兑换（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')]*(n+1) dp[0]=0 for i in range(1,n+1): for j in coins: if i>=j: dp[i]=min(dp[i-j]+1,dp[i]) if dp[n]==float('inf'): return -1 return dp[n] def main(): coins=list(map(int,input().split())) n=int(input()) res=coinsChange(coins,n) print(res) if __name__=="__main__": main()