RL-Notes

Appearance

On this page

动态规划 ​

动态规划的核心是将重复的子解存储起来，每一次要递归求值的时候，先判断有无缓存，有则取出返回，无则进入递归，并且将计算结果缓存起来。

核心就是一个缓存思想

难点在于写暴力递归求解(包含状态转移方程的实现)的过程。

求解动态规划的核心问题是穷举。因为要求最值，肯定要把所有可行的答案穷举出来，然后在其中找最值呗

递归法核心步骤 ​

  1. 判断递归方程有哪几种返回情况

    一般来说有，缓存有直接返回，递归基类时候返回，答案返回

  2. 函数主体的内部，通过状态转移方程（递归）获取合适返回值

  3. 返回答案

js
let dp = {};
var coinChange = function (coins, amount) {
  for (const coin of coins) {
    dp[coin] = 1;
  }
  return getCoinsNum(coins, amount);
};
function getCoinsNum(coins, amount) {
  if (dp[amount]) return dp[amount];
  if (amount < 0) return -1;
  let min = Infinity;
  for (const coin of coins) {
    let sub = dp[amount - coin]
      ? dp[amount - coin]
      : getCoinsNum(coins, amount - coin);
    dp[amount - coin] = sub;
    if (sub == -1) continue;
    min = Math.min(min, sub + 1);
  }
  return min == Infinity ? -1 : min;
}

迭代法核心步骤 ​

  1. 定义状态数组 dp 来存储子问题的解

  2. 遍历 dp 数组,根据状态转移方程更新 dp 数组的值

  3. 返回 dp 数组中的最终答案

java
int coinChange(int[] coins, int amount) {
    int[] dp = new int[amount + 1];
    // 数组大小为 amount + 1，初始值也为 amount + 1
    Arrays.fill(dp, amount + 1);

    // base case
    dp[0] = 0;
    // 外层 for 循环在遍历所有状态的所有取值
    for (int i = 0; i < dp.length; i++) {
        // 内层 for 循环在求所有选择的最小值
        for (int coin : coins) {
            // 子问题无解，跳过
            if (i - coin < 0) {
                continue;
            }
            dp[i] = Math.min(dp[i], 1 + dp[i - coin]);
        }
    }
    return (dp[amount] == amount + 1) ? -1 : dp[amount];
}