动态规划框架

动态规划一般用来解最值问题，其核心问题是穷举。需要在暴力穷举的过程中发现重叠子问题，然后使用备忘录记录，以避免重复计算。

动态规划问题一定会具备最优子结构，通过子问题的最值得到原问题的最值。

找到重叠子问题与最优子结构之后，还需要找到正确的状态转移方程才可以进行正确的穷举。

其中，最困难的是找到正确的状态转移方程。

明确 base case -> 明确「状态」-> 明确「选择」 -> 定义 dp 数组/函数的含义

框架如下：

1
2
3
4
5
6
7
# 初始化 base case
dp[0][0][...] = base
# 进行状态转移
for 状态1 in 状态1的所有取值：
    for 状态2 in 状态2的所有取值：
        for ...
            dp[状态1][状态2][...] = 求最值(选择1，选择2...)

零钱兑换（力扣322）

题目

给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。

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

示例 1：

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

输入：coins = [2], amount = 3
输出：-1
示例 3：

输入：coins = [1], amount = 0
输出：0
示例 4：

输入：coins = [1], amount = 1
输出：1
示例 5：

输入：coins = [1], amount = 2
输出：2

分析

从题目看，是求组成总金额的最少硬币个数。可以较容易的找出子问题：

即凑成总金额硬币个数最少 =（总金额-各面额数）+ 1 最小，一直递归直到base case。base case为最后剩余钱数（总金额-各面额数）为0。

状态转移方程如下所示：

dfs(x)={−1n<00n=0min⁡{dfs(n−coin)+1∣coin∈coins}n>0dfs(x)= \begin{cases} -1&n<0 \\ 0&n=0 \\ \min\{dfs(n-coin)+1|coin \in coins\}&n>0 \end{cases}

这样即可写出暴力递归

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def change(self, amount: int, coins: List[int]) -> int:
        def dfs(amount):
            res = float("inf")
            if amount == 0:return 0
            if amount < 0:return -1
            for coin in coins:
                sub = dfs(amount - coin)
                if sub == -1:continue
                res = min(res, 1 + sub)
            return res if res != float("inf") else -1
        return dfs(amount)

然后将重复计算使用字典保存,即可将时间复杂度降为O(kn)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def change(self, amount: int, coins: List[int]) -> int:
        memo = {}
        def dfs(amount):
            res = float("inf")
            if amount == 0:return 0
            if amount < 0:return -1
            for coin in coins:
                sub = dfs(amount - coin)
                if sub == -1:continue
                res = min(res, 1 + sub)
            memo[n] = res if res != float("inf") else -1
            return mem0[n]
        return dfs(amount)

零钱兑换II（力扣518）

题目

给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。

示例 1:

输入: amount = 5, coins = [1, 2, 5]
输出: 4
解释: 有四种方式可以凑成总金额:
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1
示例 2:

输入: amount = 3, coins = [2]
输出: 0
解释: 只用面额2的硬币不能凑成总金额3。
示例 3:

输入: amount = 10, coins = [10]
输出: 1

思路：字典判断个数即可,小于等于1个则返回True

1
2
3
4
5
6
7
8
9
from collections import Counter
class Solution:
    def canPermutePalindrome(self, s: str) -> bool:
        temp = Counter(s)
        count = 0
        for i in temp:
            if temp[i]%2 == 1:
                count += 1
        return count <= 1

参考