resin-notes
算法

动态规划

动态规划题解与思路梳理

动态规划(DP)的核心是:把大问题拆成重叠子问题,用状态定义 + 转移方程 + 边界条件求解。

本分组收录各类 DP 题解,例如:

  • 背包问题(0/1、完全、多重)
  • 线性 DP(最长上升子序列、编辑距离)
  • 区间 / 树形 / 状压 DP

爬楼梯

先看问题,要得结果是什么?是一个数字,多少种方法。说明 return a num 每一个台阶都和前一个和前两个有关系,就要想到动态规划(想不到面试就给了-_-) 有了这思想以后就会发现它可以将一个大的问题不断的拆成多个重复的小问题,也就符合了递归的概念

递归的套路
dfs(n){
  if(){}//判断
  dfs(n-1)
  dfs(n-2)
}
dfs(n)

以上是递归的模板,那现在就是去找这个递归要返回什么,然后临界是什么,因为我们结果要一个数 那么判断return的,一定是一个数字。那就是找极限情况,当n为1的时候,只有1种情况,那是不是判断就是return 1了 所以就是

if (n <= 1) {
  return 1;
}

为什么要n<=1?以后不准在判断里写n==1,只有不等或者大于小于才可以!!!(不要纠结这个,不要钻牛角尖) 到目前为止,临界值处理好了,代码继续往下执行,刚才说当前状态受前1个或者前2个影响,每一个状态记录前1或2的状态到当前的状态的次数 那说明,dfs(n)=dfs(n-1)+dfs(n-2) 那么就是

function fn(n) {
  function dfs(n) {
    if (n <= 1) {
      return 1;
    }
    return dfs(n - 1) + dfs(n - 2);
  }
  return dfs(n);
}

好,当你写到这里然后去提交的时候,你就发现了,超时了,咪的天呀!!! 看来递归还是太耗费时间了!那得换一个方法了 既然不用递归,那我们就要用一个变量去记录每一个台阶要return得数字 数组最合适了,const dp = new Array(n+1),为什么要n+1呢,(记住就好,习惯,方便) dp[1]=1,dp[2]=2,为什么要初始化这两个呢?因为当前台阶返回数和前两个有关 循环从3开始,dp[i]=dp[i-1]+dp[i-2],return dp[n]

function climbStairs(n) {
  if (n <= 2) return n; //处理边界
  //声明变量记录和边界初始化
  const dp = new Array(n + 1);
  dp[1] = 1;
  dp[2] = 2;
  //处理正常逻辑,从3开始
  for (let i = 3; i <= n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2];
  }
  //返回当前的记录的值
  return dp[n];
}

杨辉三角

  1. 这个题的话,依然是当前这个层由上一层的一些数相加得到,看结果是数组嵌套数组 声明数组``res = [],最终是res.push()`
  2. 有numRows层,那就是要处理numRows层 循环到numRows结束,因为当前受上一个循环影响,所以我们一般在声明结果的时候就初始化 res = [1]
  3. 然后思路就是第一个轮次循环,index从1开始,先添加1,进入具体操作循环 for(let j = 1;j<i;j++),里面的逻辑就是当前数由上层某两个数相加 这层循环结束以后还要末尾push一个 1
var generate = function (numRows) {
  let res = [[1]];
  for (let i = 1; i < numRows; i++) {
    res.push([1]);
    for (let j = 1; j < i; j++) {
      res[i][j] = res[i - 1][j - 1] + res[i - 1][j];
    }
    res[i].push(1);
  }
  return res;
};

打家劫舍

  1. 老套路了,直接先看题目大意,不能连续,也就是ABCD只能选AC或者BD相加。 看结果要什么,最大金额,又是当前状态受以前控制,典型dp。直接声明dp为数组,数组每一个元素记录当前状态的最大值 返回结果直接return dp[n-1]
  2. 初始化dp[0] = nums[0] for循环index从1开始到nums.length
  3. 接下来进入核心代码逻辑,这个时候你就会发现
  • dp[i] = dp[i-2] + nums[i] --> 当i===3的时候,dp[3] = dp[1]+nums[3]
  • 你会发现dp[1]没有初始化,for循环也不应该从index为1开始,而是2开始,为什么? 你要时刻记住,dp[i]代表当前位子的最大值,也就是dp[i]一定是Math.max(xx,xx)的形式的 所以dp[i] = Math.max(dp[i-2]+nums[i],dp[i-1]),那么for循环就要从index为2开始 目前还要记住,dp[1]也是index为1位子的最大值,而不是nums[1],所以这个地方也要比较大小
  1. 如果实在不理解,就记住一句话,你声明的dp数组每一个元素(dp[i])的含义是什么
var rob = function (nums) {
  const n = nums.length;
  if (n === 0) return 0;
  if (n === 1) return nums[0];
  const dp = new Array(n);
  dp[0] = nums[0];
  dp[1] = Math.max(nums[0], nums[1]);
  for (let i = 2; i < n; i++) {
    dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
  }
  return dp[n - 1];
};

完全平方数

第一步:先看问题,要得结果是什么?

看看题目:给你一个整数 n,你要返回最少数量的完全平方数。 说明 return a num。

找状态转移:在爬楼梯里,你发现“每一个台阶都和前一个和前两个有关系”。 那这道题呢?当前数字 n 是由什么变来的? 仔细想想,n 可以由 n - 1(减掉 1 的平方)变来,也可以由 n - 4(减掉 2 的平方)变来,也可以由 n - 9(减掉 3 的平方)变来…… 所以,当前状态 n,受它前面无数个“减去平方数”的状态影响。

有了这思想以后,就发现它可以将一个大的问题不断地拆成多个重复的小问题,也就符合了递归的概念。

递归的套路
dfs(n){
  if(){}//判断
  dfs(n - 1*1)
  dfs(n - 2*2)
  dfs(n - 3*3)
  // ... 直到减不动为止
}

第二步:套用递归模板,找边界与返回值

以上是递归模板,那现在就是去找这个递归要返回什么,然后临界是什么? 因为我们要的是最少个数(一个数字),所以判断 return 的,一定是一个数字。

那就是找极限情况:

当 n 变成 0 的时候,说明刚好凑齐了,不需要再加平方数了,return 0。

当 n 变成负数的时候(比如 n=2,去减 4),说明这条路走不通,返回一个很大的数字(比如 Infinity),代表“死路”。

为什么会死路?如果你减过头了(负数),说明选的那个平方数太大了,得换个小点的。 所以,递归代码写出来就是这样:

function numSquares(n) {
  function dfs(remain) {
    // 边界:刚好凑齐
    if (remain === 0) return 0;
    // 边界:减过头了,死路一条,返回无限大
    if (remain < 0) return Infinity;

    let minCount = Infinity;

    // 尝试用每一个平方数去减
    // 为什么这里 i*i <= remain 就停止?因为如果用 i*i 减,剩余是负数,就没必要试了
    for (let i = 1; i * i <= remain; i++) {
      let subResult = dfs(remain - i * i);
      // 如果这条路走得通,我们就取最小的
      minCount = Math.min(minCount, subResult + 1);
    }
    return minCount;
  }

  return dfs(n);
}

好,当你写到这里然后去提交的时候,你就发现了,超时了,咪的天呀!!! 比如 n=12,它有 4+4+4,也有 9+1+1+1,递归会像个树枝一样疯狂分叉,重复算无数次。

第三步:既然不用递归,那我们就用数组记录!

看来递归还是太耗费时间了!那得换一个方法了。 既然不用递归,那我们就要用一个变量去记录每一个数字要 return 得数字。 数组最合适了,const dp = new Array(n + 1),为什么要 n+1 呢?(记住就好,习惯,方便)。

dp 数组里装什么?装“凑成这个数字所需的最少平方数个数”。 那怎么初始化呢?我们需要一个最大值来后续更新最小值。所以我们全部初始化为 Infinity。 dp[0] = 0,这是咱们的命根子,凑成 0 需要 0 个平方数。

接下来我们要遍历了: 外层循环遍历每一个数字 i(从 1 到 n,代表当前要凑的数字)。 内层循环遍历平方数 j*j(从 1 开始,只要 j*j <= i 就继续),这相当于在尝试“当前数字减去这个平方数,剩下的数字最优解是什么”。

状态转移方程就是:dp[i] = Math.min(dp[i], dp[i - j*j] + 1) 意思就是:当前的最优解,等于“减去某个平方数后的最优解 + 1”。

第四步:最终的 DP 代码(完美继承你的数组思路)

function numSquares(n) {
  // 处理边界,如果是0直接返回0
  if (n <= 0) return 0;

  // 声明变量记录和边界初始化
  const dp = new Array(n + 1).fill(Infinity);
  dp[0] = 0; // 凑成0需要0个平方数

  // 处理正常逻辑,外层从1开始(爬楼梯你是从3开始,这里得从1开始推)
  for (let i = 1; i <= n; i++) {
    // 内层遍历所有可能的平方数
    // 为什么是 j*j <= i?因为不能减过头呀,跟递归里的条件一模一样!
    for (let j = 1; j * j <= i; j++) {
      dp[i] = Math.min(dp[i], dp[i - j * j] + 1);
    }
  }

  // 返回当前的记录的值
  return dp[n];
}

核心解释

一、 先搞懂 dp[i] 和 dp[i - j*j] + 1 是什么

我们拿 i = 12 来举例。 我们要算 dp[12],也就是“凑成 12 所需的最少平方数个数”。

看 j 的循环:j 从 1 开始,只要 j\*j <= 12 就继续。所以 j 只能取 1, 2, 3。

当 j = 1,j\*j = 1,尝试用 1 去凑 12。

当 j = 2,j\*j = 4,尝试用 4 去凑 12。

当 j = 3,j\*j = 9,尝试用 9 去凑 12。

看 Math.min(dp[i], dp[i - j*j] + 1) 在干什么:

当 j=2,意味着我们决定用掉一个 4。那么剩下的数字就是 12 - 4 = 8。

如果我们知道“凑成 8 最少需要 dp[8] 个平方数”,那么凑成 12 的答案就应该是 dp[8] + 1(因为额外多用了 4 这一个)。

同理,如果用掉一个 9,剩下的就是 3,答案就是 dp[3] + 1。

二、 为什么要用 Math.min?为什么要初始化为 Infinity?

因为你要求的是“最少”的数量! 我们在遍历 j 的时候,是在尝试不同的方案。

方案 A:用完 4 之后,剩下的凑法是 dp[8](假设等于 2),那么总共2+1=3个。

方案 B:用完 9 之后,剩下的凑法是 dp[3](假设等于 3),那么总共3+1=4个。

我们要 3 个,不要 4 个,所以用 Math.min 取最小的那个。

那为什么要把数组初始化为 Infinity? 因为我们假设一开始还没找到任何方案,先记一个“无穷大(无解)”。如果后续找到了某个方案,就可以把值更新得更小。初始化成 0 就全完蛋了,因为 0 比谁都小,Math.min 永远返回 0。

零钱兑换

一、目标拆解与数据类型映射

先问自己三个问题(这是你转型 AI 全栈必须养成的肌肉记忆):

要返回什么? 一个数字(最少硬币数),不是所有方案,不是方案列表。

求什么? 最小(不是最大、不是计数)。

有“重复子问题”吗? 有!amount=11 的答案,依赖 amount=10/9/6 的答案。

于是题型判定:最优化 DP(完全背包变种),状态是“金额”,值是“最少硬币数”。

二、直觉起步:先想想“最笨”的写法

第一次见这题,正常人(包括我)第一反应是暴力递归:

// 暴力 DFS:对每个金额,枚举所有硬币,取最小
function dfs(coins, amount) {
  if (amount === 0) return 0; // 刚好凑完
  if (amount < 0) return Infinity; // 凑过头了,废
  let min = Infinity;
  for (const c of coins) {
    min = Math.min(min, dfs(coins, amount - c) + 1);
  }
  return min;
}

这个其实就是上一题的变体,这个时候你注意,dp[i]代表的是个数 然后dp里面的i是金额,外层循环遍历金额,内层循环遍历数组里面的数 dp[i]=Math.min(dp[i-arr[j]]+1,dp[i])

/**
 * @param {number[]} coins 硬币面额数组
 * @param {number} amount 目标金额
 * @return {number} 最少硬币数,凑不出返回 -1
 */
var coinChange = function (coins, amount) {
  // 边界:0 元不需要任何硬币
  if (amount === 0) return 0;

  // dp[i] = 凑出金额 i 所需的最少硬币数
  // 初始化为 Infinity,代表"暂时凑不出"
  const dp = new Array(amount + 1).fill(Infinity);
  dp[0] = 0; // 地基:凑 0 元要 0 枚

  // 从金额 1 一路打到 amount
  for (let i = 1; i <= amount; i++) {
    // 遍历每一种硬币(注意从 0 开始!)
    for (let j = 0; j < coins.length; j++) {
      const c = coins[j];

      // 关键守卫:只有 i >= c 时,才可能用这枚硬币
      // 否则 dp[i - c] 是 undefined,会算出 NaN 污染整张表
      if (i - c >= 0) {
        // dp[i - c] + 1:用掉这一枚 c 之后的方案数 + 这一枚
        dp[i] = Math.min(dp[i], dp[i - c] + 1);
      }
    }
  }

  // 如果还是 Infinity,说明这个金额根本凑不出来(比如 coins=[2], amount=3)
  return dp[amount] === Infinity ? -1 : dp[amount];
};

单词拆分

第 1 步

  • 返回布尔
  • 要的结果是能不能拆,而不是怎么拆

第 2 步

我拿字典里的每个词,去 s 里面找一找,找到了就把它从 s 里抠掉,最后看看 s 是不是空了。

s = "cars"
wordDict = ["car", "ca", "rs"]
拿 "car" 找 → 在开头找到 → 抠掉 → s 变成 "s"
拿 "ca" 找 → 没了
拿 "rs" 找 → 没了
s = "s" 不为空 → 返回 false ❌

错了吧! 因为你一旦先抠了 "car",就把正确答案 "ca" + "rs" 的可能性给堵死了。这说明「贪心地找到就抠」这个策略根本不对——你需要在每个位置都试一遍所有可能的词,试错了要能退回来。

回溯

既然「找到就抠」不行,那最直觉的暴力解法就是——回溯:

从字符串开头开始,尝试用字典里每一个词去匹配,能匹配上就往下走,走不通就退回来换下一个词。 我用 s = "leetcode", wordDict = ["leet", "code"] 给你画一下决策树:

dfs(0) 从下标 0 开始
│
├─ 试 "leet" → s[0..4] = "leet" ✅ 匹配!
│   └─ dfs(4) 从下标 4 开始
│       ├─ 试 "leet" → s[4..8] = "code" ❌ 不匹配
│       └─ 试 "code" → s[4..8] = "code" ✅ 匹配!
│           └─ dfs(8) → 下标 8 == s.length ✅ 到头了!返回 true 🎉
│
└─ 试 "code" → s[0..4] = "leet" ❌ 不匹配
var wordBreak = function (s, wordDict) {
  const wordSet = new Set(wordDict); // 用 Set 查词 O(1)
  function dfs(i) {
    if (i === s.length) return true;
    for (const word of wordSet) {
      if (s.startsWith(word, i)) {
        if (dfs(word.length + i)) return true;
      }
    }
    return false;
  }
  return dfs(0);
};

跑一下 s = "leetcode" 是能出 true 的,但你要是拿 s = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaab", wordDict = ["a", "aa", "aaa"] 去测——咪的天呀,超时了!!! 😭

为啥?因为它会把所有「切 a 的方式」全试一遍,光是「拆一串 a」就有指数级的组合。这就是重复计算:dfs(5)、dfs(6) 会被反复算好几遍。我们加上缓存记录

记录缓存

var wordBreak = function (s, wordDict) {
  const wordSet = new Set(wordDict); // 用 Set 查词 O(1)
  const memo = new Map();
  function dfs(i) {
    if (i === s.length) return true;
    if (memo.has(i)) return memo.get(i);
    for (const word of wordSet) {
      if (s.startsWith(word, i)) {
        memo.set(i, true);
        if (dfs(word.length + i)) return true;
      }
    }
    return memo.set(false);
    return false;
  }
  return dfs(0);
};

300. 最长递增子序列

dp[i] = 以 nums[i] 结尾的最长递增子序列长度

var lengthOfLIS = function (nums) {
  const n = nums.length;
  if (n === 0) return 0; // 空数组直接返回 0,别瞎跑

  // 初始化:每个人至少能自己成一条长度为 1 的子序列
  const dp = new Array(n).fill(1);

  for (let i = 0; i < n; i++) {
    // 回头看所有 j < i
    for (let j = 0; j < i; j++) {
      // 只有 nums[j] < nums[i] 时,我才能接在它后面(严格递增)
      if (nums[j] < nums[i]) {
        dp[i] = Math.max(dp[i], dp[j] + 1);
      }
    }
  }

  // 全局最长的那条,不一定以最后一个元素结尾,所以扫一遍取 max
  return Math.max(...dp);
};

// 测试一下
console.log(lengthOfLIS([10, 9, 2, 5, 3, 7, 101, 18])); // 应该输出 4

最长公共子序列

var longestCommonSubsequence = function (text1, text2) {
  const m = x.length;
};

On this page