动态规划-零钱兑换-leetcode518
题目来源:
https://leetcode-cn.com/problems/coin-change-2/
问题描述:
解题思路:
三种硬币[1,2,5]凑成10元钱,可以理解成两种硬币[1,2]和0个5元凑成10元,或者两种硬币[1,2]和1个5元凑成10元,或者两种硬币[1,2]和2个5元凑成10元。也就是用[1,2]凑成0,5,10元。
二维数组dp[i][j]表示,i个币种凑成j元的方法数。比如dp[0][0]=1,dp[0][...]=0
用数学归纳的思想,第i行j列的方法数可以由i-1行和j-k*coins[i-1]列的方法数相加
这里的k要取到j/coins[i-1]的商
用动态规划foriforjfork,计算dp数组每一个位置的方法数,题目所求即为数组最右下方的方法数,即dp[-1][-1]
python代码: