思路和算法

定义dp
dp[j]：凑足金额j所需硬币最少个数。
dp[j]可以拆解为2个子问题：偷或者不偷：
当前金额j需加1个硬币来凑，当前金额为j - coins[i]，总硬币数：dp[j] = dp[j - coins[i]] + 1
当前金额不需要加硬币来凑。
初始化
凑足总金额为0所需硬币的个数一定是0，所以dp[0] = 0

复杂度分析

• 时间复杂度：O(n)。
• 空间复杂度：O(n)。