fat-cat

动态规划

动态规划先解决子问题，再逐步解决大问题。如果某一问题有很多重叠子问题，使用动态规划是最有效的解决方法

• 动态规划中的每一个状态一定是由上一个状态推导出来的，这一点区别于贪心算法，贪心算法没有状态推导，而是从局部直接选最优的

例如，有 N 件物品和一个最多能背重量为 W 的背包。第 i 件物品的重量是 weight[i]，得到的价值是 value[i]，每件物品只能用一次，求解将那些物品装入背包后物品价值的总和最大？

• 动态规划中的 dp[j] 是由 dp[j - weight[i]]，然后取 max(dp[j], dp[j - weight[i]] + value[i]) 的值
• 如果是贪心算法，则每次选物品时取一个最大的或者最小的值，和上一个状态没有关系。所以贪心算法解决不了动态规划的问题

对于动态规划问题，下面将其拆解为如下“五部曲”：

• 确定 dp 数组（dp table）及下标的含义
• 确定递推公式
• 初始化 dp 数组
• 确定遍历顺序
• 举例推导 dp 数组

tips: 做动态规划的题目，写代码之前一定要把状态转在 dp 数组中具体情况模拟一遍，做到心中有数，确定最后推导出的是想要的结果

绘制网格

用于解决这个问题的网格是什么样的呢？要确定这一点，得回答如下问题

• 单元格中的值是什么
• 如何将这个问题划分为子问题
• 网格的坐标轴是什么

斐波那契数列

F(0)=0，F(1)=1，F(n)=F(n - 1) + F(n - 2)

解法一

const fabonacci = (n) => {
    if(n <=1) return 0

    const dp = new Array(n + 1)

    dp[0] = 0
    dp[1] = 1

    for(let i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2]
    }

    return dp[i]
}

// 时间复杂度：O(n)
// 空间复杂度：O(n)

优化版

const fabonacci = (n) => {
    if(n <=1) return 0

    const dp = new Array(2)

    dp[0] = 0
    dp[1] = 1

    for(let i = 2; i <= n; i++) {
        let sum = dp[0] + dp[1]
        dp[0] = dp[1]
        dp[1] = sum
    }

    return dp[1]
}

// 时间复杂度：O(n)
// 空间复杂度：O(1)

背包问题

假如你是个小偷，背着一个可装 4 磅东西的背包，你可盗窃的商品有如下 3 件， 让盗窃的商品价值最高，该选择哪些商品

• 音响， 3000 元， 4 磅
• 笔记本电脑，2000 元， 3 磅
• 吉他，1500 元，1 磅

解析，横坐标为 1~4 磅的背包容量

• 确定 dp[i][j]: 从下标为 0~i 的物品中取任意物品并放进容量为 j 的背包的价值总和
• 确定递推公式
  • dp[i - 1][j]: 容量为 j，里面不放物品 i 的最大价值，此时 dp[i][j] = dp[i - 1][j]，i = 2, j = 2 dp[1][2] = dp[0][2]
  • dp[i - 1][j - weights[i]]（dp[2 - 1][ - weight[2]]）：容量为 j - weights[i] 时不放物品 i 的最大价值，那么 物品 i 的最大价值为 dp[i - 1][j - weights[i]] + value[i]

y\x	1	2	3	4
音响(A)	0	0	0	3000(A)
笔记本电脑(B)	0	0	2000(B)	3000(A)
吉他(C)	1500(C)	1500(C)	1500(C)	2000 + 1500= 4500(B+C)

const getMaxProfit = (costs = [3000, 2000, 1500], weights = [4, 3, 1], maxWeight = 4) => {
    const planLen = costs.length // 3
    const dp = [[]]

    for (let x = 0; x <= maxWeight; x++) dp[0][x] = x < weights[0] ? 0 : costs[0]
    for (let x2 = 1; x2 < planLen; x2++) {
        dp[x2] = new Array(maxWeight)
        dp[x2][0] = 0
    }

    // x 代表物品行
    for (let x = 1; x < planLen; x++) {
    // y 代表重量
        for (let y = 1; y <= maxWeight; y++) {
            const weight = weights[x] // x=1, weight=3

            // 物品重量 > 背包容量，表示放不下
            if (weight > y) dp[x][y] = dp[x - 1][y] // dp[1][1]= dp[0][1] 等于 同重量下，上一个较重物品的价值
            // 物品重量 < 背包容量，表示放得下，计算剩余背包容量的价值
            else dp[x][y] = Math.max(dp[x - 1][y], costs[x] + dp[x - 1][y - weight])
        }
    }

    return dp[planLen][maxWeight]
}

console.log(getMaxProfit())

最长公共子串

hish 和 fish 的最长公共子串

• 如果两个字母不相同，值为 0
• 如果两个字母相同，值为左上角单元格的值 + 1

*	H	I	S	H
F	0	0	0	0
I	0	1	0	0
S	0	0	2	0
H	0	0	0	3

最长公共子序列

不小心输入了 fosh， 那原本是想输入 fish 还是 fort？

• 如果两个字母不同，值为上方和左方邻居中较大的那个
• 如果两个字母相同，值为左上方单元格的值 + 1

*	F	O	S	H
F	1	1	1	1
I	1	1	1	1
S	1	1	2	2
H	1	1	2	3

*	F	O	S	H
F	1	1	1	1
O	1	2	2	2
R	1	2	2	2
T	1	2	2	2