322. 零钱兑换

Powered by:NEFU AB-IN

Link

322. 零钱兑换

题意

给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。

计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。

你可以认为每种硬币的数量是无限的。

思路

完全背包的变种，物品价值为1
再说一下完全背包的记忆化搜索，因为每种物品可以随便选，那么在选了i之后，i是不变的，表示可以继续选这个物品，dfs(i, w - coins[i]) + 1

代码

# 3.8.9 import
import random
from collections import Counter, defaultdict, deque
from datetime import datetime, timedelta
from functools import lru_cache, reduce
from heapq import heapify, heappop, heappush, nlargest, nsmallest
from itertools import combinations, compress, permutations, starmap, tee
from math import ceil, comb, fabs, floor, gcd, hypot, log, perm, sqrt
from string import ascii_lowercase, ascii_uppercase
from sys import exit, setrecursionlimit, stdin
from typing import Any, Callable, Dict, List, Optional, Tuple, TypeVar# Constants
TYPE = TypeVar('TYPE')
N = int(2e5 + 10)
M = int(20)
INF = int(1e12)
OFFSET = int(100)
MOD = int(1e9 + 7)# Set recursion limit
setrecursionlimit(int(2e9))class Arr:array = staticmethod(lambda x=0, size=N: [x() if callable(x) else x for _ in range(size)])array2d = staticmethod(lambda x=0, rows=N, cols=M: [Arr.array(x, cols) for _ in range(rows)])graph = staticmethod(lambda size=N: [[] for _ in range(size)])class Math:max = staticmethod(lambda a, b: a if a > b else b)min = staticmethod(lambda a, b: a if a < b else b)class Std:pass# ————————————————————— Division line ——————————————————————class Solution:def coinChange(self, coins: List[int], amount: int) -> int:n = len(coins)@lru_cache(None)def dfs(i: int, w: int) -> int:if i < 0:return 0 if w == 0 else INFif w < coins[i]:return dfs(i - 1, w)return Math.min(dfs(i - 1, w), dfs(i, w - coins[i]) + 1)ans = dfs(n - 1, amount)return ans if ans < INF else -1