BAT 面试钟爱的动态规划类问题，如何掌握？

[hakunamatata11]

作为动态规划类问题中非常重要的一个类别，背包问题已经慢慢地成为了面试高频题。

这道面试题，把背包换成了别的词就直接拿出来用了，但是很多人都在这道题上，跪了......

现在我们一起来学习一下这道题。

题目描述

给出不同面额的硬币以及一个总金额，写一个方法来计算给出的总金额可以换取的最少的硬币数量. 如果已有硬币的任意组合均无法与总金额面额相等, 那么返回-1.

样例 1

输入：
[1, 2, 5]
11
输出：3
解释：11 = 5 + 5 + 1

样例 2

输入： 
[2]
3
输出： -1

说明

这是一个典型的完全背包问题。 设 dp[i][j]表示使用前 i 个硬币，总金额为 j 时需要的最少硬币数量。

# This reference program is provided by @jiuzhang.com
# Copyright is reserved. Please indicate the source for forwarding

class Solution:
    """
    @param coins: a list of integer
    @param amount: a total amount of money amount
    @return: the fewest number of coins that you need to make up
    """
    def coinChange(self, coins, amount):
        # write your code here
        MAX = 100000000000000
        ans = [MAX for i in range(amount + 1)]
        ans[0] = 0
        for i in range(1, amount + 1):
            for coin in coins:
                if i - coin < 0:
                    continue
                ans[i] = min(ans[i], ans[i - coin] + 1)
        if ans[amount] == MAX:
            return -1;
        return ans[amount];

此为 Python 解法，Java，C++解法见Lincode

如果你没认出这是背包问题，最好去听一听《背包四讲》，基础知识和刷题都覆盖到了。

这门原价$199 的课程，现在：

戳我免费试听后，加微信号 jiuzhang15，回复「 V2EX 背包」+试听截图，即可免费获得本课程~