动态规划

概念¶

“ Dynamic programming is a technique that is sometimes considered the opposite of recursion.”

递归自顶向下，假设整个问题已解决，再解决小问题；
动态规划 自底向上，先解决小问题，然后把它们组合起来，成为整个问题的解。

思想¶

一个问题的最优解，是由它各个子问题的最优解决定的。

将一个大问题，拆成若干子问题
计算每个子问题的最优解
根据这些解，得出大问题的最优解

问题属性¶

最优子结构 Optimal Substructure
- 状态转移方程 f(n)
重叠子问题 Overlapping Sub-problems

求解关键问题¶

如何定义 f(n)
如何通过 f(1), f(2), ..., f(n - 1) 推导出 f(n)，即 状态转移方程。

300. 最长上升子序列¶

状态转移方程:

f(n) = max{ f(i) } + 1，其中 (1 <= i <= n - 1 且 nums[i - 1] < nums[n - 1])

递归实现 Recursion¶

/**
 * @param {number[]} nums
 * @return {number}
 */
var lengthOfLIS = function(nums) {
  let solution = {};

  f(nums, nums.length, solution);

  // console.log(solution.list);
  return solution.list.length;
};

// 状态转移函数
function f(nums, n, solution) {
  if (n === 0) {
    solution.list = [];
    return [];
  }

  let maxHere = [nums[n - 1]];
  if (n === 1) {
    solution.list = maxHere;
    return maxHere;
  }

  for (let i = 1; i <= n - 1; i++) {
    let result = f(nums, i, solution);

    if(nums[i - 1] < nums[n - 1] && maxHere.length < result.length + 1) {
      maxHere = [...result, nums[n - 1]];
    }
  }

  if (solution.list.length < maxHere.length) {
    solution.list = maxHere;
  }

  return maxHere;
}

时间复杂度计算 T(n) = T(n - 1) + T(n - 2) + ... T(1)
T(n) = O(2^n)

记忆化实现 Memorization¶

将已经计算好的结果，保存起来

问题分类¶

线性规划 Linear Programming
区间规划 Interval Programming
约束规划 Constraint Programming

线性规划¶

子问题的规模以线性方式存在；
可用一维线性表（数组，哈希表），保存子问题的最优状态或结果；
通常 dp[i] 表示第 i 个位置的结果，或从 0 到 1 的最优状态。

198. 打家劫舍¶

状态转移方程 f(n) = max{ f(n-1), f(n - 2) + nums[n] }
递推公式 dp[i] = max{ dp[i - 1], dp[i - 2] + nums[i] }

/**
 * @param {number[]} nums
 * @return {number}
 */
var rob = function(nums) {
  let n = nums.length;

  if (n === 0) {
    return 0;
  }
  if (n === 1) {
    return nums[n - 1];
  }

  const dp = [];
  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];
};

62. 不同路径¶

递推公式： dp[i][j] = dp[i - 1][j] + dp[i][j - 1]

/**
 * @param {number} m
 * @param {number} n
 * @return {number}
 */
var uniquePaths = function(m, n) {
  // TO DO
};

区间规划¶

子问题的规模，由不同的区间来决定；
可用二维数组，保存子问题的最佳状态或结果；

516. 最长回文子序列¶

假设 d[i][j] 表示从字符 i 到 j 之间的最长回文。

递推公式，若首位字符相等，dp[0][n - 1] = dp[1][n - 2] + 2；

否则，dp[0][n - 1] = max{ dp[0][n - 2], dp[1][n - 1] }。

/**
 * @param {string} s
 * @return {number}
 */
var longestPalindromeSubseq = function(s) {
  let n = s.length;
  let dp = Array.from({ length: n }).map(i =>  Array.from({ length: n }));

  // 对角线元素设为1，表示单个字符回文长度为1
  for(let i = 0; i < n; i++) {
    dp[i][i] = 1;
  }

  for(let i = n - 1; i >= 0; i--) {
    for (let j = i + 1; j <n; j++) {
      if (s[i] === s[j]) {
        // 若首尾相等，则加2
        dp[i][j] = (dp[i + 1][j - 1] || 0) + 2;
      } else {
        // 若不等，则在左下两个矩阵中（更小规模的字符串中），取最大值
        dp[i][j] = Math.max(dp[i + 1] && dp[i + 1][j] || 0, dp[i][j - 1] || 0);
      }
    }
  }

  return dp[0][n - 1];
};

约束规划¶

非决定性多项式
0-1 背包问题

经典问题¶

1. Fibonacci 数列¶

递归解法¶

递归函数多次被调用，形成一个递归树，事实上在内存中运行效率极其低下。

function recurFib(n) {
  if (n < 2) {
    return n;
  } else {
    return recurFib(n-1) + recurFib(n-2);
  }       
}

动态规划解法¶

使用 val 数组来存储中间结果

// 动态规划解法
function dynFib(n){
  const val = Array(n).fill(0);

  if (n === 1 || n === 2) {
    return 1;
  }

  val[1] = 1;
  val[2] = 2;
  for (var i = 3; i <= n; ++i) {
    val[i] = val[i - 1] + val[i - 2];
  }

  return val[n - 1];
}

2. 最长公共子串¶

寻找两个字符串中最长公共子串 (Longest Common Substring) 是动态规划的经典问题。
算法思想：用二维数组记录两个字符串在相同位置的字母的比较结果。
- 1) 二维数组初始化为全0；
- 2) 每次两个字符串相同位置匹配时，二维数组相应位置加1，否则置0。

function lcs(word1, word2){
  var max = 0;     // 公共子串最大长度
  var index = 0;   // 标记公共子串位置

  var lcsarr = new Array(word1.length);  // 声明 lcsarr 矩阵，并初始化   

  for(var i = 0; i < word1.length; i++){
    lcsarr[i] = new Array(word2.length);
    for(var j = 0; j < word2.length; j++){
      lcsarr[i][j] = 0; 
    }
  }

  for(var i = 0; i < word1.length; i++){
    for(var j = 0; j < word2.length; j++){
      if(word1[i] == word2[j]) {
        if (i == 0 || j == 0) {
          lcsarr[i][j] = 1;
        } else {
          lcsarr[i][j] = lcsarr[i-1][j-1] + 1;
        }

        if (max < lcsarr[i][j]) {
          max = lcsarr[i][j]; 
          index = i;
        }
      }
    }
  }

  //console.log(lcsarr)
  return word1.substr(index - max + 1, max);
}

3. 背包问题¶

背包问题 (Knapsack Problem)：一堆物品，各有 value 和 size 两个属性，背包限定抓取物品 size 的总大小，如何让所选之物总值 value 最大。
假设有如下物品：

var capacity = 16;           // 背包大小
var n = 5;                   // 物品数量
var value = [4,5,10,11,13];  // 物品价值
var size = [3,4,7,8,9];      // 物品大小

递归解法¶

/**
 * Return 背包内物品价值总和
 * */ 
function knapsack(capacity, n, size, value) {
   // 递归终止条件
  if(capacity == 0 || n == 0) {
    return 0;  
  }

  // 若装不下，则弃之
  if(size[n-1] > capacity) {
    return knapsack(capacity, n-1, size, value)
  }

  const a = knapsack(capacity, n-1, size, value);
  const b = knapsack(capacity - size[n-1], n-1, size, value) + value[n-1];

  return a > b ? a : b;
}

动态规划解法¶

算法思想：用二维矩阵记录背包和物品在扩张过程中的最优解。
矩阵用二维数组 K[i][j] 表示，i ∈ [0, …, n]，j ∈ [0, …, capacity]。

function dKnapsack(capacity, n, size, value){
  const K = []; // 声明矩阵并初始化
  for(var i = 0; i <= n; i++)  {
    K[i] = [];
  }

  for(var i = 0; i <= n; i++){
    for(var j = 0; j <= capacity; j++){
      if(i == 0 || j == 0) {
        K[i][j] = 0; 
      } else if (j < size[i-1]) {
        K[i][j] = K[i-1][j] 
      } else {
        const a = K[i-1][j];
        const b = K[i-1][j-size[i-1]]+value[i-1];
        K[i][j] = a > b ? a : b;
      }
    }
  }

  return K[n][capacity];
}