vlambda博客
学习文章列表

动态规划-零钱兑换-leetcode518

题目来源:

https://leetcode-cn.com/problems/coin-change-2/




问题描述:




动态规划-零钱兑换-leetcode518



解题思路:

  1. 三种硬币[1,2,5]凑成10元钱,可以理解成两种硬币[1,2]和0个5元凑成10元,或者两种硬币[1,2]和1个5元凑成10元,或者两种硬币[1,2]和2个5元凑成10元。也就是用[1,2]凑成0,5,10元。

  2. 二维数组dp[i][j]表示,i个币种凑成j元的方法数。比如dp[0][0]=1,dp[0][...]=0

  3. 用数学归纳的思想,第i行j列的方法数可以由i-1行和j-k*coins[i-1]列的方法数相加

    这里的k要取到j/coins[i-1]的商

  4. 用动态规划foriforjfork,计算dp数组每一个位置的方法数,题目所求即为数组最右下方的方法数,即dp[-1][-1]






python代码: