动态规划常见思路

date
Dec 10, 2020
slug
dp
status
Published
tags
数据结构与算法
summary
动态规划常见思路
type
Post
  • 常见形式:求最值,如最长递增子序列呀,最小编辑距离
  • 核心问题:穷举

动态规划三要素

重叠子问题

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

最优子结构

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

状态转移方程

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

框架

明确base case->明确状态->明确选择->定义dp数组/函数
# 初始化 base case
dp[0][0][...] = base
# 进行状态转移
for 状态1 in 状态1的所有取值:
    for 状态2 in 状态2的所有取值:
        for ...
            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),这就是动态规划的思路,这也是为什么动态规划都脱离了递归,由循环迭代完成都原因。
const fib = (N) => {
    if (N < 1) return 0;
    if (N == 1 || N == 2) return 1;
    const dp = Array(N+1).fill(0);
    // base case
    dp[1] = dp[2] = 1;
    for (let i = 3; i <= N; i++){
    		dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[N];
}

状态压缩

如果发现每次状态转移只需要dp table中的一部分,那可以尝试状态压缩来调整dp table的大小。如上题,当前状态只和前两个状态有关,就不用一个dp table来存储所有状态了。
const fib = (N) => {
    if (N < 1) return 0;
    if (N == 1 || N == 2) return 1;
    let prev = 1, curr = 1;
    // base case
    for (let i = 3; i <= N; i++){
    		let sum = prev + curr;
        prev = curr;
        curr = sum;
    }
    return dp[N];
}

凑零钱问题

给你 k 种面值的硬币,面值分别为 c1, c2 ... ck,每种硬币的数量无限,再给一个总金额 amount,问你最少需要几枚硬币凑出这个金额,如果不可能凑出,算法返回 -1 。算法的函数签名如下:
  • base case: amout=0->return 0
  • 状态:amount
  • 选择:不同的硬币
  • dp: dp(n) 传入金额,返回最少硬币数量

递归解法

const coinChange = (coins, amount) => {
		# 备忘录
    let memo = {};
    # 定义:要凑出金额 n,至少要 dp(n) 个硬币
    this.dp = n => {
        if(memo[n] !== undefined){
            return memo[n];
        }
        if(n===0){
            return 0;
        }
        if(n<0){
            return -1;
        }
        #求最小值,所以初始化infinity
        let res = Infinity;
        for(let coin of coins){
        		# 子问题
            let subRes = dp(n - coin);
            #子问题无解,跳过
            if(subRes == -1) {
                continue;
            }
            res=Math.min(res, 1 + subRes );
        }
        memo[n] = res !== Infinity ? res : -1;
        return memo[n];
    }
    return dp(amount)
}

dp解法

const coinChange =(coins,amount) => {
    // 数组大小为 amount + 1,初始值为正无穷
    const dp = Array(amount + 1).fill(Infinity);
    // base case
    dp[0] = 0;
    // 外层 for 循环在遍历所有状态的所有取值
    for (int i = 0; i < dp.length(); i++) {
        // 内层 for 循环在求所有选择的最小值
        for (let coin of coins) {
            // 子问题无解,跳过
            if (i - coin < 0) continue;
            dp[i] = min(dp[i], 1 + dp[i - coin]);
        }
    }
    return (dp[amount] == Infinity) ? -1 : dp[amount];
}

最长上升子序列

给定一个无序的整数数组,找到其中最长上升子序列的长度
示例:
输入: [10,9,2,5,3,7,101,18]
输出: 4
解释: 最长的上升子序列是 [2,3,7,101],它的长度是 4。
  • base case: 1 因为最短就是自身
  • 状态:数组
  • 选择:不同的子序列
  • dp:传入数组,返回最长子序列长度
var lengthOfLIS = function(nums) {
	#时间复杂度O(N^2)
    const dp = Array(nums.length).fill(1);
    for(let i = 0; i< nums.length; i++) {
        for(let j=0; j<i; j++){
            if(nums[j] < nums[i]){
                dp[i] = Math.max(dp[i],dp[j]+1);
            }
        }
    }
    let res = 0;
    for(let i =0; i< dp.length; i++) {
        res = Math.max(res,dp[i]);
    }
    return res;
};

编辑距离

给你两个单词 word1 和 word2,请你计算出将 word1 转换成 word2 所使用的最少操作数 。
你可以对一个单词进行如下三种操作:
插入一个字符 删除一个字符 替换一个字符
示例 :
输入:word1 = "horse", word2 = "ros"
输出:3
解释:
horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')
notion image
  • base case:i走完s1或j走完s2,直接返回剩下字符串的长度
  • 对于每对比较的字符,会有如下操作:
if s1[i] == s2[j]:
    啥都别做(skip),
    i, j 同时向前移动
else:
    三选一:
      插入(insert)
        dp(i, j - 1) + 1,    # 插入
        # 在 s1[i] 插入一个和 s2[j] 一样的字符
        # 那么 s2[j] 就被匹配了,前移 j,继续跟 i 对比
      删除(deletedp(i - 1, j) + 1,    # 删除
        # 把 s[i] 这个字符删掉
        # 前移 i,继续跟 j 对比
      替换(replace)
        dp(i - 1, j - 1) + 1 # 替换
        # 我直接把 s1[i] 替换成 s2[j],这样它俩就匹配了
        # 同时前移 i,j 继续对比
  • dp:返回 s1[0..i] 和 s2[0..j] 的最小编辑距离
var minDistance = function (word1, word2) {
      const m = word1.length, n =word2.length;
      #dp table
      const dp = Array(m+1).fill(0).map(() => new Array(n+1).fill(0));
      for(let i = 1; i<=m; i++){
        dp[i][0] =i ;
      }
      for(let j = 1; j<=n; j++){
        dp[0][j] =j ;
      }
      for(let i=1; i<=m; i++){
        for(let j=1; j<=n; j++){
          if(word1.charAt(i-1) == word2.charAt(j-1)){
            dp[i][j] = dp[i - 1][j - 1]
          } else {
            dp[i][j] = Math.min(
              dp[i-1][j]+1,
              dp[i][j-1]+1,
              dp[i-1][j-1]+1
            )
          }
        }
      }
      return dp[m][n]
    };

高楼丢鸡蛋

var superEggDrop = function (K, N) {
      const memo = Array(K + 1).fill(-1).map(() => new Array(N + 1).fill(-1));
      this.dp = (K, N) => {
        if (K == 1) return N;
        if (N == 0) return 0;
        if(memo[K][N]!== -1) return memo[K][N]
        let res = Infinity;
        let lo = 1, hi = N;
        while (lo <= hi) {
          let mid = Math.floor((lo + hi) / 2);
          let broken = dp(K - 1, mid - 1);
          let not_broken = dp(K, N - mid);
          if (broken > not_broken) {
            hi = mid - 1
            res = Math.min(res, broken + 1)
          } else {
            lo = mid + 1
            res = Math.min(res, not_broken + 1)
          }
        }
        memo[K][N] = res
        return memo[K][N];
      }
      return dp(K,N);
    };

最长回文子序列

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
notion image
notion image
notion image
if (s[i] == s[j])
    // 它俩一定在最长回文子序列中
    dp[i][j] = dp[i + 1][j - 1] + 2;
else
    // s[i+1..j] 和 s[i..j-1] 谁的回文子序列更长?
    dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);
var longestPalindromeSubseq = function(s) {
      const n = s.length;
      const dp = [];
      for(let i = 0; i < n; i++) {
        dp[i] = [];
        for(let j = 0; j < n; j++) {
          if(i === j) {
            dp[i][j] = 1;
          } else {
            dp[i][j] = 0;
          }
        }
      }
      for(let i = n-1; i>=0; i--){
        for(let j=i+1; j<n;j++) {
          if(s[i] === s[j]) {
            dp[i][j] = dp[i+1][j-1] + 2;
          } else {
            dp[i][j] = Math.max(dp[i+1][j],dp[i][j-1])
          }
        }
      }
      return dp[0][n-1]
    };

石子游戏

亚历克斯和李用几堆石子在做游戏。偶数堆石子排成一行,每堆都有正整数颗石子 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 分。
var stoneGame = function (piles) {
      let { length } = piles, dp = new Array(length)
      // 初始化
      for (let i = 0; i < length; ++i) {
        dp[i] = new Array(length)
        for (let j = 0; j < length; ++j) {
          dp[i][j] = new Array(2).fill(0)
        }
      }
      for (let i = 0; i < length; ++i) {
        dp[i][i][0] = piles[i]
      }

      /**
       *  定义三维DP:
       *  dp[i][j][k]: 在区间[i, j]中先手(k = 0)或后手(k = 1)可获得的最高分数
       *
       *  dp[i][j][0] = max(piles[i] + dp[i + 1][j][1], piles[j] + dp[i][j - 1][1])
       *  先手选择首个
       *  dp[i][j][1] = dp[i + 1][j][0]
       *  先手选择尾个
       *  dp[i][j][1] = dp[i][j - 1][0]
       */
      for (let i = 1; i < length; ++i) {
        // 求解手画更为清晰
        for (let j = 0; j < length - i; ++j) {
          // dp[j][j + i][0]
          let leftVal = piles[j] + dp[j + 1][j + i][1] // 先手选择完首个后转为后手
          let rightVal = piles[j + i] + dp[j][j + i - 1][1] // 先手选择完尾个后转为后手
          if (leftVal >= rightVal) {
            dp[j][j + i][0] = leftVal
            dp[j][j + i][1] = dp[j + 1][j + i][0] // 后手转先手
          } else {
            dp[j][j + i][0] = rightVal
            dp[j][j + i][1] = dp[j][j + i - 1][0] // 后手转先手
          }
        }
      }
      console.log(dp)
      return dp[0][length - 1][0] > dp[0][length - 1][1]
    };

贪心算法之区间调度问题

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

notion image
 var intervalSchedule = function (intervals) {
      if(intervals.length === 0) return 0;
      //按end排序
      intervals.sort((a,b)=>{
        if(a[1]<b[1]) {
          return -1;
        } else if(a[1] > b[1]) {
          return 1;
        } else {
          return 0;
        }
      })
      //计数 至少有一个区间不相交
      let count = 1;
      //排序后,第一个区间设为x区间
      let x_end = intervals[0][1];
      for(let i of intervals){
        //每个区间的start
        const start = i[0];
        if(start >= x_end) {
          count++;
          x_end = i[1];
        }
      }
      console.log(intervals);
      return count;
    };

股票问题

dp[3][2][1] 的含义就是:今天是第三天,我现在手上持有着股票,至今最多进行 2 次交易。再比如 dp[2][3][0] 的含义:今天是第二天,我现在手上没有持有股票,至今最多进行 3 次交易
状态转移方程
dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i])
              max(   选择 rest  ,             选择 sell      )
解释:今天我没有持有股票,有两种可能:
要么是我昨天就没有持有,然后今天选择 rest,所以我今天还是没有持有;
要么是我昨天持有股票,但是今天我 sell 了,所以我今天没有持有股票了。
dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i])
              max(   选择 rest  ,           选择 buy         )
解释:今天我持有着股票,有两种可能:
要么我昨天就持有着股票,然后今天选择 rest,所以我今天还持有着股票;
要么我昨天本没有持有,但今天我选择 buy,所以今天我就持有股票了。
base case
dp[-1][k][0] = 0
解释:因为 i 是从 0 开始的,所以 i = -1 意味着还没有开始,这时候的利润当然是 0 。
dp[-1][k][1] = -infinity
解释:还没开始的时候,是不可能持有股票的,用负无穷表示这种不可能。
dp[i][0][0] = 0
解释:因为 k 是从 1 开始的,所以 k = 0 意味着根本不允许交易,这时候利润当然是 0 。
dp[i][0][1] = -Infinity
解释:不允许交易的情况下,是不可能持有股票的,用负无穷表示这种不可能。
base case:
dp[-1][k][0] = dp[i][0][0] = 0
dp[-1][k][1] = dp[i][0][1] = -Infinity
状态转移方程:
dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i])
dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i])
 

© kaba 2019 - 2022