1
class Solution:
2
    def coinChange(self, coins: List[int], amount: int) -> int:
3
        # 初始化备忘录，-2表示尚未计算
4
        self.memo = [-2] * (amount + 1)
5
        return self.dp(coins, amount)
6

7
    def dp(self, coins, amount):
8
        # base case：目标金额为0
9
        if amount == 0:
10
            return 0
11
        # base case：目标金额为负，表示无解
12
        if amount < 0:
13
            return -1
14
        # 如果已经计算过，直接返回备忘录的值
15
        if self.memo[amount] != -2:
16
            return self.memo[amount]
17

18
        res = float('inf')
19
        for coin in coins:
20
            sub = self.dp(coins, amount - coin)
21
            # 如果子问题无解，跳过
22
            if sub == -1:
23
                continue
24
            res = min(res, sub + 1)
25

26
        # 保存子问题结果到备忘录
27
        self.memo[amount] = -1 if res == float('inf') else res
28
        return self.memo[amount]

1
class Solution:
2
    def numSquares(self, n: int) -> int:
3
        # 初始化dp数组，dp[i]表示组成i的最少完全平方数数量
4
        dp = [float('inf')] * (n + 1)
5
        dp[0] = 0  # 和为0时需要0个数
6

7
        # 外层遍历背包容量
8
        for i in range(1, n + 1):
9
            # 内层遍历所有平方数物品
10
            for j in range(1, int(i**0.5) + 1):
11
                # 状态转移：dp[i] = min(dp[i], dp[i - j*j] + 1)
12
                dp[i] = min(dp[i], dp[i - j * j] + 1)
13

14
        return dp[n]

1
class Solution:
2
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
3
        # 初始化备忘录，-1表示未计算，0表示false，1表示true
4
        self.memo = [-1] * len(s)
5
        return self.dp(s, 0, wordDict)
6

7
    def dp(self, s, i, wordDict):
8
        # 如果从第i个字符开始可以成功拆分，返回True
9
        if i == len(s):
10
            return True
11
        # 如果已经计算过，直接返回结果
12
        if self.memo[i] != -1:
13
            return self.memo[i] == 1
14

15
        for word in wordDict:
16
            length = len(word)
17
            # 如果剩余长度不足一个单词，跳过
18
            if i + length > len(s):
19
                continue
20
            # 取出s中从i开始、长度为length的子串
21
            sub = s[i:i + length]
22
            if sub != word:
23
                continue
24
            # 如果子问题成功，记下结果并返回
25
            if self.dp(s, i + length, wordDict):
26
                self.memo[i] = 1
27
                return True
28

29
        # 所有尝试都失败，记为false
30
        self.memo[i] = 0
31
        return False