在准备面试的过程中发现之前漏掉了一些算法的整理,在本文中慢慢补齐
动态规划
太抽象,还是以零钱问题为例吧。
其实凡是涉及到这种重叠子问题的,都可以用动态规划。
重叠子问题是啥意思?就是大问题拆解成的小问题,可以递归+缓存,比如电影院第几排或者斐波拉契数列,自顶向下,肯定会有部分重叠子问题,如果用缓存,drill down的时候缓存起来。缺点是什么:这样其实还是会去遍历,只能会再走缓存,性能强一些。
有时候,可以递归+贪心,比如零钱,先从最大面额的开始递归,提高性能。
有没有更厉害的解法?就是动态规划。听着挺唬人的,其实就那样。先按照零钱问题走一遍。
初始化状态 -> 确定状态参数 -> 设计决策的思路
初始化是什么,就是amount=0,需要的最小硬币数,dp[0]=0
然后其他每个的初始值都是 dp[i]=Integer.MAX_VALUE
(只需要比amount大就行)
然后是状态参数。啥意思?子问题和原问题之间发生变化的变量。状态参数是dp[j]
,它记录了达到金额j
所需的最少硬币数量。
然后就是设计决策,状态转移方程,描述了如何从已知状态推导出未知状态的过程。要怎么逐步获取到我们要的结果dp[amount]
呢?对于每种硬币coin
,考虑将其加入到构成总金额的过程中。对于每一个j >= coin
,我们检查如果使用了一个面值为coin
的硬币,那么剩余的金额变为j - coin
。如果dp[j - coin]
已经有了一个有效的值(即不是Integer.MAX_VALUE
),说明存在一种方式可以凑成j - coin
,那么我们就可以通过增加一个coin
硬币来考虑凑成j
的方案,即更新dp[j] = min(dp[j], dp[j - coin] + 1)
。这里dp[j - coin] + 1
意味着在已有凑成j - coin
最少硬币数基础上再加一个硬币。
我们从最小的金额开始,逐步向上构建,直到求得目标金额amount
所需的最少硬币数。每一步的决策都是基于之前的最优解,确保了最终得到的是全局最优解。
对应代码
public class Solution322 {
public int coinChange(int[] coins, int amount) {
int[] dp = new int[amount + 1];
// 初始化
Arrays.fill(dp, amount + 1);
dp[0] = 0;
// 状态方程
for (int i = 1; i <= amount; i++) {
for (int coin : coins) {
if (coin <= i) {
dp[i] = Math.min(dp[i], dp[i-coin]+1);
}
}
}
return dp[amount] == amount+1 ? -1:dp[amount];
}
}