动态规划常见思路

date

Dec 10, 2020

slug

status

Published

动态规划三要素

重叠子问题

如果暴力穷举的话效率十分低下，所以需要一个备忘录或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')

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 对比
      删除（delete）
        dp(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

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. 用最少数量的箭引爆气球

 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])