浅浅地学习动态规划...

什么是动态规划？

在现实生活中，有一类活动的过程，由于它的特殊性，可将过程分成若干个互相联系的阶段，在它的每一阶段都需要作出决策，从而使整个过程达到最好的活动效果。因此各个阶段决策的选取不能任意确定，它依赖于当前面临的状态，又影响以后的发展。

对于这种问题，决策依赖当前的状态，又影响以后的发展。那么把复杂的问题分成一个个子问题，子问题解决并保存结果的求解复杂问题的方法称为动态规划。

解题思路

1. 确定状态

   即最后一步和子问题。

   • 最后一步：是指解决该问题，最优策略的最后一步是什么？
   • 子问题：通过解析最后一步，可以将问题分解成一个个的最后一步，即子问题。

2. 转移方程

   一般可通过子问题获得转移方程。

3. 初始条件和边界情况

   看题目具体情况。

4. 计算顺序

   看具体题目情况，一维一般从左到右，二维一般从上到下，从左到右。

题目特点

1. 计数
   • 有多少种方式走到右下角。
   • 有多少种方法选出k个数使和为sum。
2. 求最大最小值
   • 从左上到右下角路径最大和。
   • 最长上升子序列长度。
3. 求存在性
   • 取石子，先手是否必胜？
   • 能否选k个数使和是sum。

例题

1. coin change

给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。

如输入coins = [2, 5, 7]和amount = 27，答案为5。

解析

a[i]表示凑成金额i所需的最少硬币数。

1. 确定状态

   最后一步：手里只有2、5和7三种硬币，最后一步也一定是产生于这三个硬币中的一个，即27 = (27 - coin) + coin，a[27] = a[27 -coin] + 1。倒数第二步27 - coin也必须是最少硬币数，才能保证最后一步是硬币最少数。

   子问题：用最少的硬币拼出amount - coin。

2. 转移方程

   a[amount] = Math.min(a[amount -2] + 1, a[amount -5] + 1, a[amount -7] + 1)

3. 初始条件和边界情况

   初始条件：a[0] = 0，a[2] = 1，a[5] = 1，a[7] = 1。

   边界情况：(amount - coin) >= 0

4. 计算顺序

   由于后续的答案需要前面的结果，前面的结果需要保存，因此从左至右。

代码

function countCoins(amount, coins) {
  const maxNum = Math.ceil(amount / 2); // 最多用这么多硬币
  const arr = Array.from({ length: amount + 1 }); // 初始化数组[0, 1, ..., amount]
  arr[0] = 0; // 初始条件

  for (let i = 1; i < arr.length; i++) {
    arr[i] = maxNum;
    for (let j = 0; j < coins.length; j++) {
      if (i >= coins[j]) arr[i] = Math.min(arr[i], arr[i - coins[j]] + 1); // 状态转移
    }
  }
  return arr[amount];
}
1
2
3
4
5
6
7
8
9
10
11
12
13

2. 不同的路径

有一个机器人的位于一个 m × n个网格左上角。

机器人每一时刻只能向下或者向右移动一步。机器人试图达到网格的右下角。

问有多少条不同的路径？

如输入m=3,n=3，输出6。

解析

a[m][n]代码第m行第n列有多少种不同的路径。

1. 确定状态

   最后一步：机器人只能来自于向下或者向右移动一步，即a[m][n] = a[m][n-1] + a[m-1][n]。

   子问题：a[i][j]有多少种不同的路径。

2. 转移方程

   a[m][n] = Math.max(a[m][n-1] + a[m-1][n], a[m][n])。

3. 初始条件和边界情况

   初始条件：a[0][0] = 1。

   边界情况：0 <= i <= m, 0 <= j <= n。

4. 计算顺序

   每一个格子，需要拿到上和左的数据，但当算到当前的时候，左数据其实已经拿到了。因此从上到下，从左至右。

代码

function calcNums(m, n) {
  // 二维数组初始化
  let arr = new Array();
  for (let i = 0; i < m; i++) {
    arr[i] = new Array();
  }

  // 计算
  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      if (i === 0 && j === 0) {
        arr[0][0] = 1;
        continue;
      }
      arr[i][j] = 0;
      num1 = i >= 1 ? arr[i - 1][j] : 0;
      num2 = j >= 1 ? arr[i][j - 1] : 0;
      arr[i][j] = Math.max(num1 + num2, arr[i][j]);
    }
  }
  return arr[m - 1][n - 1];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

3. 跳跃游戏

给出一个非负整数数组，你最初定位在数组的第一个位置。

数组中的每个元素代表你在那个位置可以跳跃的最大长度。

判断你是否能到达数组的最后一个位置。

解析

f[i]表示是否能够到达第i个位置，值为布尔。

1. 确定状态

   最后一步：倒数第二步满足足够条件跳到最后一步，即n - i <= jump且能够到达倒数第二步i。

   子问题：是否能够到达第i个位置。

2. 转移方程

   f[i] = f[j] && i-j <= jump[j]，其中0<=i。

3. 初始条件和边界情况

   初始条件：f[0] = true。

4. 计算顺序

   后面的数据需要前面，从左至右。

function finishJump(arr) {
  const resArr = [];
  resArr.length = arr.length;
  resArr.fill(false);
  resArr[0] = true;
  for (let j = 1; j < arr.length; j++) {
    for (let i = 0; i < j; i++) {
      if (resArr[i] && arr[i] + i >= j) {
        resArr[j] = true;
        break;
      }
    }
  }
  return resArr[resArr.length - 1];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

function minOptionCount(word1, word2) {
  const length1 = word1.length + 1;
  const length2 = word2.length + 1;
  // initation
  const box = Array.from({ length: length1 });
  const arr = box.map((item) =>
    Array.from({ length: length2 }, (item2) => Number.MAX_VALUE)
  ); // 二位数组长宽都加了1，因为(0,0)

  // calculate
  for (let i = 0; i < length1; i++) {
    for (let j = 0; j < length2; j++) {
      // two boundaries
      if (i * j === 0) {
        // i = 0 or j = 0
        arr[i][j] = i + j; // initation
      } else {
        // state transition
        arr[i][j] =
          word1[i - 1] === word2[j - 1] // 当单词一样时，操作数无需加1。
            ? arr[i - 1][j - 1]
            : Math.min(
                arr[i][j],
                Math.min(arr[i][j - 1], arr[i - 1][j], arr[i - 1][j - 1]) + 1
              );
      }
    }
  }
  return arr[length1 - 1][length2 - 1];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30