动态规划介绍和示例

简言

动态规划介绍和使用示例。
动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中，可能会有许多可行解。每一个解都对应于一个值，我们希望找到具有最优值的解。动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。

动态规划（Dynamic Programming，DP）

动态规划（Dynamic Programming，简称DP）是一种求解最优化问题的算法思想，尤其适用于具有重叠子问题和最优子结构性质的问题。其基本思想是通过把原问题分解为相互重叠的子问题来降低问题复杂度，并保存这些子问题的解以避免重复计算，从而最终构造出原问题的解。

思路

动态规划的主要步骤包括：

1. 确定状态：明确问题中需要进行决策的关键要素以及与时间、空间等有关的状态变量。

2. 定义状态转移方程：明确如何从一个状态转移到另一个状态，即如何通过已知的子问题的解来推导出更大规模子问题的解。

3. 初始状态或边界条件：确定递归树的叶子节点或者最简单情况下的状态值。

4. 根据状态转移方程填充状态表（或数组），自底向上或自顶向下地计算所有状态的值。

5. 根据状态表得出原问题的解。

用途

动态规划广泛应用在计算机科学、数学、经济学等领域，常见的动态规划问题有背包问题、最长公共子序列、最短路径问题（如Dijkstra算法、Bellman-Ford算法）、矩阵链乘法、区间调度问题等等。

相关术语

• 阶段：把所给求解问题的过程恰当地分成若干个相互联系的阶段，以便于求解，过程不同，阶段数就可能不同。描述阶段的变量称为阶段变量。
• 状态：状态表示每个阶段开始面临的自然状况或客观条件，它不以人们的主观意志为转移，也称为不可控因素。
• 决策：一个阶段的状态给定以后，从该状态演变到下一阶段某个状态的一种选择（行动）称为决策。在许多问题中，决策可以自然而然地表示为一个数或一组数。不同的决策对应着不同的数值。描述决策的变量称决策变量，因状态满足无后效性，故在每个阶段选择决策时只需考虑当前的状态。
• 策略：由每个阶段的决策组成的序列称为策略。
• 无后效性：我们要求状态具有下面的性质：如果给定某一阶段的状态，则在这一阶段以后过程的发展不受这阶段以前各段状态的影响，所有各阶段都确定时，整个过程也就确定了。状态的这个性质意味着过程的历史只能通过当前的状态去影响它的未来的发展，这个性质称为无后效性。

局限性

它没有统一的处理方法，必须根据问题的各种性质并结合一定的技巧来处理；另外当变量的维数增大时，总的计算量及存贮量急剧增大。

示例

斐波那契数列

题目

给定一个整数n，计算F(n)，其中F(n)是斐波那契数列的第n项，定义如下：

• F(0) = 0
• F(1) = 1
• 对于n > 1,F(n) = F(n-1) + F(n-2)

斐波那契数列使用递归计算时会有大量重复计算内容，可以使用动态规划优化计算过程。

分析

F(0) ，F(1),F(n)的值是 “状态” 。
F(0)求值、F(1)求值、F(n)求值 是“阶段”。
F(n) = F(n-1) + F(n-2) 是“决策”。
所以求F(n)的值，我们需要把F(1)~F(n)值存起来就是策略。

示例

创建一个数组 arr 来存储斐波那契数列的每一项，避免重复计算。初始化 arr[0] 和 arr[1]，然后通过循环从第二项开始计算每一项的值。

/**
 *  动态规划-斐波那契数列
 * @param {number } n
 * @returns
 */
function dynamicFS(n) {
  if (n <= 0) return 0;
  if (n <= 1) return 1;

  let arr = [0, 1]; // f(n) 值数组
  for (let i = 2; i <= n; i++) {
    arr[i] = arr[i - 1] + arr[i - 2];
  }
  return arr[n];
}
console.log(dynamicFS(5));

最长递增子序列（Longest Increasing Subsequence，LIS）

题目

给定一个整数数组 nums ，找出其中最长严格递增子序列的长度。

分析

整数数组nums是“状态”，要求严格递增子序列的长度L也是。
遍历每一项和前一项对比 是“阶段”。
若当前项和前一项相比符合严格递增要求，长度L加1，是“决策”。
将所有的决策保存到一个数组中并求最长的决策长度是“策略”。

示例

/**
 *  求最长递增子序列的长度
 * @param {*} nums  整数数组
 * @param {*} interval 间隔
 * @returns
 */
function dynamicMaxLen(nums, interval = 1) {
  let res = []; // 递增子序列数组
  let temp = []; //  临时存放递增子序列
  for (let i = 0; i < nums.length; i++) {
    if (nums[i] + interval === nums[i + 1]) {
      temp.push(nums[i]);
    } else {
      res.push({
        len: temp.length,
        arr: temp,
      });
      temp = [];
    }
  }
  const maxArr = res.reduce((a, b) => (a.len > b.len ? a : b)); 
  return maxArr.len;
}

console.log(
  dynamicMaxLen([
    1, 2, 1, 1, 2, 3, 4, 5, 3, 6, 7, 8, 2, 9, 10, 2, 11, 12, 2, 13, 14, 2,
  ])
);

确定硬币找零问题（Coin Change）

题目

给定不同面额的硬币和一个总金额，求解组成这个金额的最少硬币数量。例如：给定面额为 [1, 2, 5] 的硬币和总金额为 11，最少需要3个硬币（5, 5, 1）。

分析

给定面额的硬币 和 总金额 是“状态”。
求指定金额可以分成几个给定面额硬币是“阶段”。
从“阶段”多个结果数组中找到最优结果（最少硬币数）是“决策”。
将1，2，3，…指定金额值的最优结果保存到一个数组中是“策略”。

示例

这里优化了以下，
由于我们的阶段是在大于不能整除时需要前面阶段的结果，需要给定面额余数值的阶段，
所以 策略数组可以是[1,2,3…给定面额最大值,指定金额]。

/**
 *    1,2,3,4,5,6,7,8,9,10,11
 *   1 1    4
 *   2 0 1  2   3
 *   5 0 0    0        2, 11
 *
 *
 * @param {*} coins
 * @param {*} total
 * @returns
 */

function dynamicCoins(coins = [], total = 0) {
  let res = [[]]; //  存放结果  ,total=0时返[]
  let max = Math.max(...coins);
  let forArr = []; //  1,2,3,..max,total
  for (let i = 1; i < max; i++) {
    forArr.push(i);
  }
  forArr.push(total);
  for (let v = 1; v < forArr.length; v++) {
    let temp = [];
    for (let i = 0; i < coins.length; i++) {
      if (forArr[v] % coins[i] === 0) {
        //  能整除
        temp[i] = new Array(forArr[v] / coins[i]).fill(coins[i]);
      } else if (forArr[v] < coins[i]) {
        //  小于
        temp[i] = [];
      } else {
        //  大于且不能整除
        temp[i] = [
          ...new Array(Math.floor(forArr[v] / coins[i])).fill(coins[i]),
          ...res[forArr[v] % coins[i]],
        ];
      }
    }
    res[forArr[v]] = temp[0];
    //  最小值
    for (let tempV of temp) {
      if (tempV.length < res[forArr[v]].length && tempV.length > 0) {
        res[forArr[v]] = tempV;
      }
    }
    // console.log(res[v]);
  }

  return res[total];
}

console.log("最少硬币::", dynamicCoins([1, 3, 4], 22));

背包问题（Knapsack Problem

题目

给定一组物品，每种物品都有自己的重量和价值，现在有一个承重为 W 的背包，如何选择装入背包的物品，使得装入背包中物品的总价值最大。

分析

给定的一组物品 和 背包承重为W是“状态”。
求背包承重w最大价值是“阶段”。
在背包承重w求最大价值时找前面阶段承重w`最大价值是 “决策”.
将承重1,2,3…w最大价值结果保存到一个数组中是“策略”.

注意边界问题，背包有可能无法装满。

示例

/**
goods为 物品数组，goods[0][0]为重量，goods[0][1]为价值.
total为背包承重W
return 最大价值数组
*/
function dynamicBackpack(goods = [], total = 0) {
  let res = [[]];
  for (let i = 1; i <= total; i++) {
    let temp = [];
    for (let good of goods) {
      if (i % good[0] === 0) {
        temp.push(new Array(i / good[0]).fill(good[1]));
      } else if (i > good[0]) {
        temp.push([
          ...new Array(Math.floor(i / good[0])).fill(good[1]),
          ...res[Math.floor(i % good[0])], // 余数不为整数时向下取整
        ]);
      }
    }

    res[i] = [];
    for (let tempV of temp) {
      let tempVV = tempV.reduce((a, b) => a + b);
      if (tempVV > res[i].reduce((a, b) => a + b, 0)) {
        res[i] = tempV;
      }
    }
  }
  return res[total];
}
console.log(
  dynamicBackpack(
    [
      [1, 1.5],
      [2, 3.5],
      [3, 6],
    ],
    1
  )
);
console.log(
  dynamicBackpack(
    [
      [2, 1.5],
      [2, 3.5],
      [3, 6],
    ],
    10
  )
);

结语

结束了。