Skip to content
kaba

动态规划常见思路

算法1 min read

  • 常见形式:求最值,如最长递增子序列呀,最小编辑距离
  • 核心问题:穷举

动态规划三要素

重叠子问题

如果暴力穷举的话效率十分低下,所以需要一个备忘录或dp table来记录已经计算过的值,优化穷举过程 如:斐波那契数列f(20)=f(19)+f(18),f(19)=f(18)+f(17),这个f18就是一个重叠子问题,如果用一个memo保存起来,效率会快很多

最优子结构

指能够通过子问题的最值来得到原问题的最值

状态转移方程

另外,虽然动态规划的核心思想就是穷举求最值,但是问题可以千变万化,穷举所有可行解其实并不是一件容易的事,只有列出正确的「状态转移方程」才能正确地穷举。

框架

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

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

两种思想

自顶向下

斐波那契数这个递归,由上到下延伸 f(20)=f(19)+f(18),f(19)=f(18)+f(17),逐步分解直到f(2)和f(1)这两个base case,然后逐层返回答案

自底向上

直接从底部最简单的f(1)和f(2)向上推,直到推到想要的答案f(20),这就是动态规划的思路,这也是为什么动态规划都脱离了递归,由循环迭代完成都原因。

1const fib = (N) => {
2 if (N < 1) return 0;
3 if (N == 1 || N == 2) return 1;
4 const dp = Array(N+1).fill(0);
5 // base case
6 dp[1] = dp[2] = 1;
7 for (let i = 3; i <= N; i++){
8 dp[i] = dp[i - 1] + dp[i - 2];
9 }
10 return dp[N];
11}

状态压缩

如果发现每次状态转移只需要dp table中的一部分,那可以尝试状态压缩来调整dp table的大小。如上题,当前状态只和前两个状态有关,就不用一个dp table来存储所有状态了。

1const fib = (N) => {
2 if (N < 1) return 0;
3 if (N == 1 || N == 2) return 1;
4 let prev = 1, curr = 1;
5 // base case
6 for (let i = 3; i <= N; i++){
7 let sum = prev + curr;
8 prev = curr;
9 curr = sum;
10 }
11 return dp[N];
12}

凑零钱问题

给你 k 种面值的硬币,面值分别为 c1, c2 ... ck,每种硬币的数量无限,再给一个总金额 amount,问你最少需要几枚硬币凑出这个金额,如果不可能凑出,算法返回 -1 。算法的函数签名如下:

  • base case: amout=0->return 0
  • 状态:amount
  • 选择:不同的硬币
  • dp: dp(n) 传入金额,返回最少硬币数量
递归解法
1const coinChange = (coins, amount) => {
2 # 备忘录
3 let memo = {};
4 # 定义:要凑出金额 n,至少要 dp(n) 个硬币
5 this.dp = n => {
6 if(memo[n] !== undefined){
7 return memo[n];
8 }
9 if(n===0){
10 return 0;
11 }
12 if(n<0){
13 return -1;
14 }
15 #求最小值,所以初始化infinity
16 let res = Infinity;
17 for(let coin of coins){
18 # 子问题
19 let subRes = dp(n - coin);
20 #子问题无解,跳过
21 if(subRes == -1) {
22 continue;
23 }
24 res=Math.min(res, 1 + subRes );
25 }
26 memo[n] = res !== Infinity ? res : -1;
27 return memo[n];
28 }
29 return dp(amount)
30}
dp解法
1const coinChange =(coins,amount) => {
2 // 数组大小为 amount + 1,初始值为正无穷
3 const dp = Array(amount + 1).fill(Infinity);
4 // base case
5 dp[0] = 0;
6 // 外层 for 循环在遍历所有状态的所有取值
7 for (int i = 0; i < dp.length(); i++) {
8 // 内层 for 循环在求所有选择的最小值
9 for (let coin of coins) {
10 // 子问题无解,跳过
11 if (i - coin < 0) continue;
12 dp[i] = min(dp[i], 1 + dp[i - coin]);
13 }
14 }
15 return (dp[amount] == Infinity) ? -1 : dp[amount];
16}

最长上升子序列

给定一个无序的整数数组,找到其中最长上升子序列的长度 示例: 输入: [10,9,2,5,3,7,101,18] 输出: 4 解释: 最长的上升子序列是 [2,3,7,101],它的长度是 4。

  • base case: 1 因为最短就是自身
  • 状态:数组
  • 选择:不同的子序列
  • dp:传入数组,返回最长子序列长度
1var lengthOfLIS = function(nums) {
2 #时间复杂度O(N^2)
3 const dp = Array(nums.length).fill(1);
4 for(let i = 0; i< nums.length; i++) {
5 for(let j=0; j<i; j++){
6 if(nums[j] < nums[i]){
7 dp[i] = Math.max(dp[i],dp[j]+1);
8 }
9 }
10 }
11 let res = 0;
12 for(let i =0; i< dp.length; i++) {
13 res = Math.max(res,dp[i]);
14 }
15 return res;
16};

编辑距离

给你两个单词 word1 和 word2,请你计算出将 word1 转换成 word2 所使用的最少操作数 。 你可以对一个单词进行如下三种操作: 插入一个字符 删除一个字符 替换一个字符 示例 : 输入:word1 = "horse", word2 = "ros" 输出:3 解释: horse -> rorse (将 'h' 替换为 'r') rorse -> rose (删除 'r') rose -> ros (删除 'e')

image-20210207201046418

  • base case:i走完s1或j走完s2,直接返回剩下字符串的长度
  • 对于每对比较的字符,会有如下操作:
1if s1[i] == s2[j]:
2 啥都别做(skip),
3 i, j 同时向前移动
4else:
5 三选一:
6 插入(insert)
7 dp(i, j - 1) + 1, # 插入
8 # 在 s1[i] 插入一个和 s2[j] 一样的字符
9 # 那么 s2[j] 就被匹配了,前移 j,继续跟 i 对比
10 删除(delete)
11 dp(i - 1, j) + 1, # 删除
12 # 把 s[i] 这个字符删掉
13 # 前移 i,继续跟 j 对比
14 替换(replace)
15 dp(i - 1, j - 1) + 1 # 替换
16 # 我直接把 s1[i] 替换成 s2[j],这样它俩就匹配了
17 # 同时前移 i,j 继续对比
  • dp:返回 s1[0..i] 和 s2[0..j] 的最小编辑距离
1var minDistance = function (word1, word2) {
2 const m = word1.length, n =word2.length;
3 #dp table
4 const dp = Array(m+1).fill(0).map(() => new Array(n+1).fill(0));
5 for(let i = 1; i<=m; i++){
6 dp[i][0] =i ;
7 }
8 for(let j = 1; j<=n; j++){
9 dp[0][j] =j ;
10 }
11 for(let i=1; i<=m; i++){
12 for(let j=1; j<=n; j++){
13 if(word1.charAt(i-1) == word2.charAt(j-1)){
14 dp[i][j] = dp[i - 1][j - 1]
15 } else {
16 dp[i][j] = Math.min(
17 dp[i-1][j]+1,
18 dp[i][j-1]+1,
19 dp[i-1][j-1]+1
20 )
21 }
22 }
23 }
24 return dp[m][n]
25 };

高楼丢鸡蛋

1var superEggDrop = function (K, N) {
2 const memo = Array(K + 1).fill(-1).map(() => new Array(N + 1).fill(-1));
3 this.dp = (K, N) => {
4 if (K == 1) return N;
5 if (N == 0) return 0;
6 if(memo[K][N]!== -1) return memo[K][N]
7 let res = Infinity;
8 let lo = 1, hi = N;
9 while (lo <= hi) {
10 let mid = Math.floor((lo + hi) / 2);
11 let broken = dp(K - 1, mid - 1);
12 let not_broken = dp(K, N - mid);
13 if (broken > not_broken) {
14 hi = mid - 1
15 res = Math.min(res, broken + 1)
16 } else {
17 lo = mid + 1
18 res = Math.min(res, not_broken + 1)
19 }
20 }
21 memo[K][N] = res
22 return memo[K][N];
23 }
24 return dp(K,N);
25 };

最长回文子序列

dp:在子串 s[i..j] 中,最长回文子序列的长度为 dp[i][j]

想求 dp[i][j],假设你知道了子问题 dp[i+1][j-1] 的结果(s[i+1..j-1] 中最长回文子序列的长度,如果 s[i] 和 s[j] 相等,他俩加上s[i+1..j-1] 中的最长回文子序列就是 s[i..j] 的最长回文子序列;如果它俩不相等,说明它俩不可能同时出现在 s[i..j] 的最长回文子序列中,那么把它俩分别加入 s[i+1..j-1] 中,看看哪个子串产生的回文子序列更长即可

base case: i==j : 1 ; i< j : 0 image-20210207201114111

1if (s[i] == s[j])
2 // 它俩一定在最长回文子序列中
3 dp[i][j] = dp[i + 1][j - 1] + 2;
4else
5 // s[i+1..j] 和 s[i..j-1] 谁的回文子序列更长?
6 dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);
1var longestPalindromeSubseq = function(s) {
2 const n = s.length;
3 const dp = [];
4 for(let i = 0; i < n; i++) {
5 dp[i] = [];
6 for(let j = 0; j < n; j++) {
7 if(i === j) {
8 dp[i][j] = 1;
9 } else {
10 dp[i][j] = 0;
11 }
12 }
13 }
14 for(let i = n-1; i>=0; i--){
15 for(let j=i+1; j<n;j++) {
16 if(s[i] === s[j]) {
17 dp[i][j] = dp[i+1][j-1] + 2;
18 } else {
19 dp[i][j] = Math.max(dp[i+1][j],dp[i][j-1])
20 }
21 }
22 }
23 return dp[0][n-1]
24 };

石子游戏

亚历克斯和李用几堆石子在做游戏。偶数堆石子排成一行,每堆都有正整数颗石子 piles[i] 。 游戏以谁手中的石子最多来决出胜负。石子的总数是奇数,所以没有平局。 亚历克斯和李轮流进行,亚历克斯先开始。 每回合,玩家从行的开始或结束处取走整堆石头。 这种情况一直持续到没有更多的石子堆为止,此时手中石子最多的玩家获胜。 假设亚历克斯和李都发挥出最佳水平,当亚历克斯赢得比赛时返回 true ,当李赢得比赛时返回 false 。

dp: 用一个三维数组表示。dp[i][j][k]表示从i到j这部分石头,k:先手/后手能获得到最高分数

  • 假设 piles = [3, 9, 1, 2],索引从 0 开始
  • dp[0][1][0] = 9 意味着:面对石头堆 [3, 9],先手最终能够获得 9 分。
  • dp[1][3][1] = 2 意味着:面对石头堆 [9, 1, 2],后手最终能够获得 2 分。
1var stoneGame = function (piles) {
2 let { length } = piles, dp = new Array(length)
3 // 初始化
4 for (let i = 0; i < length; ++i) {
5 dp[i] = new Array(length)
6 for (let j = 0; j < length; ++j) {
7 dp[i][j] = new Array(2).fill(0)
8 }
9 }
10 for (let i = 0; i < length; ++i) {
11 dp[i][i][0] = piles[i]
12 }
13
14 /**
15 * 定义三维DP:
16 * dp[i][j][k]: 在区间[i, j]中先手(k = 0)或后手(k = 1)可获得的最高分数
17 *
18 * dp[i][j][0] = max(piles[i] + dp[i + 1][j][1], piles[j] + dp[i][j - 1][1])
19 * 先手选择首个
20 * dp[i][j][1] = dp[i + 1][j][0]
21 * 先手选择尾个
22 * dp[i][j][1] = dp[i][j - 1][0]
23 */
24 for (let i = 1; i < length; ++i) {
25 // 求解手画更为清晰
26 for (let j = 0; j < length - i; ++j) {
27 // dp[j][j + i][0]
28 let leftVal = piles[j] + dp[j + 1][j + i][1] // 先手选择完首个后转为后手
29 let rightVal = piles[j + i] + dp[j][j + i - 1][1] // 先手选择完尾个后转为后手
30 if (leftVal >= rightVal) {
31 dp[j][j + i][0] = leftVal
32 dp[j][j + i][1] = dp[j + 1][j + i][0] // 后手转先手
33 } else {
34 dp[j][j + i][0] = rightVal
35 dp[j][j + i][1] = dp[j][j + i - 1][0] // 后手转先手
36 }
37 }
38 }
39 console.log(dp)
40 return dp[0][length - 1][0] > dp[0][length - 1][1]
41 };

贪心算法之区间调度问题

452. 用最少数量的箭引爆气球

image-20210207201134144

1var intervalSchedule = function (intervals) {
2 if(intervals.length === 0) return 0;
3 //按end排序
4 intervals.sort((a,b)=>{
5 if(a[1]<b[1]) {
6 return -1;
7 } else if(a[1] > b[1]) {
8 return 1;
9 } else {
10 return 0;
11 }
12 })
13 //计数 至少有一个区间不相交
14 let count = 1;
15 //排序后,第一个区间设为x区间
16 let x_end = intervals[0][1];
17 for(let i of intervals){
18 //每个区间的start
19 const start = i[0];
20 if(start >= x_end) {
21 count++;
22 x_end = i[1];
23 }
24 }
25 console.log(intervals);
26 return count;
27 };

股票问题

dp[3][2][1] 的含义就是:今天是第三天,我现在手上持有着股票,至今最多进行 2 次交易。再比如 dp[2][3][0] 的含义:今天是第二天,我现在手上没有持有股票,至今最多进行 3 次交易

状态转移方程    

1dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i])
2 max( 选择 rest , 选择 sell )
3解释:今天我没有持有股票,有两种可能:
4要么是我昨天就没有持有,然后今天选择 rest,所以我今天还是没有持有;
5要么是我昨天持有股票,但是今天我 sell 了,所以我今天没有持有股票了。
6dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i])
7 max( 选择 rest , 选择 buy )
8解释:今天我持有着股票,有两种可能:
9要么我昨天就持有着股票,然后今天选择 rest,所以我今天还持有着股票;
10要么我昨天本没有持有,但今天我选择 buy,所以今天我就持有股票了。

base case

1dp[-1][k][0] = 0
2解释:因为 i 是从 0 开始的,所以 i = -1 意味着还没有开始,这时候的利润当然是 0 。
3dp[-1][k][1] = -infinity
4解释:还没开始的时候,是不可能持有股票的,用负无穷表示这种不可能。
5dp[i][0][0] = 0
6解释:因为 k 是从 1 开始的,所以 k = 0 意味着根本不允许交易,这时候利润当然是 0 。
7dp[i][0][1] = -Infinity
8解释:不允许交易的情况下,是不可能持有股票的,用负无穷表示这种不可能。
1base case:
2dp[-1][k][0] = dp[i][0][0] = 0
3dp[-1][k][1] = dp[i][0][1] = -Infinity
4状态转移方程:
5dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i])
6dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i])