基本流程

1、递归+记忆化——递推
2、状态的定义
3、状态转移方程
4、最优子结构

比较概念

DP vs 回溯（递归） vs 贪心
DP——记录局部最优子结构/多种记录值
回溯（递归）——重复计算
贪心——永远局部最优

实战演练

0、二维矩阵计算走法种类（存在障碍）
1、爬楼梯（每次只能走一阶或两阶）

1
2
3
f(n) = f(n - 1) + f(n - 2)
f(1) = 1
f(2) = 2

​ 其实斐波拉契数列有 O(logN)的解法

2、三角形最小路径之和(m 层)
状态定义：DP[i][j]——从底部走到[i][j]的所有路径最小和

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
// 状态转移方程：dp[i][j] = min(dp[i + 1][j], dp[i + 1][j + 1]) + triangle[i][j]
// 初始值：DP[m-1][j]=T[m-1][j]
// 返回dp[0][0]

function minPath(triangle) {
  if (triangle.length === 0) {
    return;
  }
  let dp = [];
  for (let i = 0; i < triangle.length; i++) {
    dp[i] = [];
    for (let j = 0; j < triangle[i].length; j++) {
      dp[i].push(0);
    }
  }
  // 初始化
  for (let i = 0; i < dp.length; i++) {
    dp[dp.length - 1][i] = triangle[dp.length - 1][i];
  }
  // 递归
  for (let i = dp.length - 2; i >= 0; i--) {
    for (let j = 0; j < dp[i].length; j++) {
      dp[i][j] = Math.min(dp[i + 1][j], dp[i + 1][j + 1]) + triangle[i][j];
    }
  }
  return dp[0][0];
}

3、乘积最大子序列 (2 3 -2 4)
如果不用连续
如果连续
1）暴力求解？
2）动态规划
这里的状态是二维的，不只是一维，需要同时存 max 和 min，因为元素可能为负数

1
2
3
4
5
6
DP[i, j] = [max, min]
if (a[i] > 0) DP[i, 0] = DP[i - 1, 0] _ a[i]
if (a[i] < 0) DP[i, 0] = DP[i - 1, 1] _ a[i]

if (a[i] > 0) DP[i, 1] = DP[i - 1, 1] _ a[i]
if (a[i] < 0) DP[i, 1] = DP[i - 1, 0] _ a[i]

​结果： 遍历 DP[i, 0]，找出最大值

或者直接定义两个数组也可

4、股票买卖问题7, 1, 3, 5, 2, 4, 1
1）只能买卖一次\两次\三次\k 次等等
DP[i,j]=max-profit,status

1
2
3
4
5
6
7
8
9
10
11
DP[i-1,0] //此时未买入,不动
DP[i-1,1]+a[i] //此时拥有股票,卖出
DP[i, 0] = max(DP[i - 1, 0], DP[i - 1, 1] + a[i])

DP[i-1,1] //此时拥有股票,不动
DP[i-1,0]-a[i] //此时未买入,买一股
DP[i, 1] = max(DP[i - 1, 1], DP[i - 1, 0] - a[i])

// 但是当前定义的状态还不够,如果有 k 次限制呢?
// 定义三维,增加交易的多少次
DP[i, j, k] = [max - profit, status, times]

2）买卖无数次
3）卖完必须隔 1 天买入

5 最长上升子序列(位置不变)
1)不用连续
方法 1:暴力求解
方法 2:动态规划 O(N^2)
状态定义:DP[i] 到第 i 个数(选上 i 元素)的最优子结构
结果:DP[0]到 DP[n-1]的最大值
状态转移方程:DP[i]=max(DP[j])+1 (j 从 0 到 i-1,且 a[j]<a[i])
方法 3:二分法 O(NlogN)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// dp[i] 表示以第i个元素结尾的最长上升子序列的长度
// 如果dp[i]<dp[j]+1,则dp[i]=dp[j]+1
// 初始化dp[0]=1
// 返回max(dp[0],dp[1],……,dp[n-1])的最大值
function lengthOfLIS(nums) {
  if (nums.length === 0) return 0;
  let dp = [1];
  for (let i = 1; i < nums.length; i++) {
    dp.push(0);
  }
  let LIS = 1;
  for (let i = 1; i < dp.length; i++) {
    dp[i] = 1;
    for (let j = 0; j < i; j++) {
      if (nums[i] > nums[j] && dp[i] < dp[j] + 1) {
        dp[i] = dp[j] + 1;
      }
    }
    if (LIS < dp[i]) {
      LIS = dp[i];
    }
  }
  return LIS;
}

2)要求连续(更加容易)

6 零钱兑换问题
DP[i] 表示凑成 i 的最小零钱总数
DP[i] = min(DP[i - coin[j]]) + 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// 给定4种面额的硬币1分，2分，5分，6分，如果要找11分的零钱，怎么做才能使得找的硬币数量总和最少。
// 动态方程： dp[i] = max(dp[i - 1], dp[i - 2], dp[i - 5], dp[i - 6]) + 1
function coinChange(coins, amount) {
  let dp = [];
  for (let i = 0; i <= amount; i++) {
    dp.push(-1);
  }
  dp[0] = 0;
  for (let i = 1; i <= amount; i++) {
    for (let j = 0; j < coins.length; j++) {
      if (i - coins[j] >= 0 && dp[i - coins[j]] !== -1) {
        if (dp[i] === -1 || dp[i] > dp[i - coins[j]] + 1) {
          dp[i] = dp[i - coins[j]] + 1;
        }
      }
    }
  }
  return dp[amount];
}

7 背包问题
01 背包 完全背包 多重背包
1)01 背包

1
2
3
4
dp( i,j ) = Max( dp( i-1, j ), dp( i-1, j-w[i] ) + v[i] )
// DP[k,w]表示当背包容量还剩 w 时,在前 k 个物品中选择的最大价值
DP[k, w] = DP[k - 1, w] //(当第 k 件过重, 超出总容量)
DP[k, w] = max(DP[k - 1, w], DP[k - 1][w(总) - w(k)] + v[k]) //前者表示放入第 k 个物品, 后者表示不放入第 k 个物品 2)完全背包 3)多重背包