V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
hakunamatata11
V2EX  ›  推广

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

  •  
  •   hakunamatata11 · 2020-03-26 17:11:00 +08:00 · 891 次点击
    这是一个创建于 1463 天前的主题,其中的信息可能已经有所发展或是发生改变。

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

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

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

    题目描述

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

    样例 1

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

    样例 2

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

    说明

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

    image

    # 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 背包」+试听截图,即可免费获得本课程~

    目前尚无回复
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   1044 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 24ms · UTC 19:17 · PVG 03:17 · LAX 12:17 · JFK 15:17
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.