1. 三角形最小路径和

image.png

以dp[i][j]表示以i, j 位置的点为起点到达最低端的最小路径的和
状态方程：dp[i][j] = triangle[i][j] + min(dp[i+1][j], dp[i+1][j+1])
边界：i 到达最后一行

// 这里只写了思路，可以再缓存一下结果优化递归调用
function minTrace(triangle) {
    var lth = triangle.length;
    if(!lth) { return 0;}
    if (lth === 1) {
        return triangle[0][0];
    }
    const minTr = function(i, j) {
        if (i === lth - 1) { return triangle[i][j]; }  // 边界  
        return triangle[i][j] + Math.min(minTr(i + 1, j), minTr(i + 1, j + 1));
    }
    return minTr(0, 0);
}

2. 字符串的编辑问题

image.png

dp[i][j]表示的是：strA的前i下标位的字符变化到strB的前j下标位字符的编辑距离

        if (a[i] === b[j]) {
          dp[i][j] =  dp(i - 1, j - 1); // 如果2个字符相等，编辑距离不会增加       
        }

        let v1 = dp(i - 1, j - 1) + 1, // 替换
            v2 = dp(i, j - 1) + 1, // 删除
            v3 = dp(i - 1, j ) + 1; // 插入

       dp[i][j] = Math.min(v1, v2, v3);

image.png	-	-
情况1：替换 image.png	-情况2：删除 image.png	-情况3： 插入 image.png

3. 字符串中回文子串的数量

image.png

dp[i, j] 表示字符串从i到j位是否是回文，值标记为布尔值
如果str[i] !== str[j]，则dp[i][j] = false
如果str[i] === str[j]， 则 dp[i][j]取决于dp[i+1][j-1]是否为true

一些边界条件：
当i === j即只有一个字符时，是回文
当j-i === 1 && str[i] === str[j]即只有2个字符且他俩相等时，是回文

image.png

4. 字符串中的最长回文子串的长度

仍是上题的思路，修改点是当str[i, j]是回文时,dp[i][j]存字符长度，不是回文时dp[i][j] = 0

let i = lth // i从最后一位往前遍历
let dp = []; // dp[i, j]：从i到j位的字符如果是回文，就存字符长度，如果不是，就为0
while (i >= 0) {
    if (!dp[i]) {
        dp[i] = {};
    }
    let j = i; // 这里很重要，我们定义j>=i，则j从i开始往后遍历
    while (j <= lth) {
        if (i === j) {
            // 如果只有一个字符串，就是回文，长度为1
            dp[i][j] = 1;
        } else if (j - i === 1 && line[i] === line[j]) {
            // 如果是2个字符串且2个字符相等，就是回文，长度为2
            dp[i][j] = 2;
        } else if (line[i] === line[j] && dp[i + 1][j - 1] > 0) {
            // 3个字符及以上
            dp[i][j] = 2 + dp[i + 1][j - 1]; // 这2个字符的长度+str[i+1][j-1]的长度
        }
        j++;
    }
    i--;
}
let max = 0;
dp.forEach(d => {
    Object.values(d).forEach(v => {
        if (v > max) { max = v }
    })
});
// console.log(dp)
console.log(max)

5. 合唱队

N 位同学站成一排，音乐老师要请最少的同学出列，使得剩下的 K 位同学排成合唱队形。

• 请最少的人出列，即求人数最多的合唱队形
• 计算每位同学左侧的最长递增子序列的长度，以及右侧的最长递减子序列的长度
• 这个题最主要的是要明确：如何求i之前 / 之后的最长递增/递减子序列
• 如果 dp[i]表示i之前的最长递增子序列的长度，那么dp[i] = 1 + max (i前面每一个小于它的项的最长递增子序列的长度)

image.png

6. 字符串中最长回文子序列的长度

需要跟子串区别的是，子串是连续的，子序列可以不连续

• dp[i][j]表示从i到j位的最长回文子序列的长度
• 当str[i] === str[j]时，dp[i][j] = dp[i+1][j-1]+2
• 当str[i] !== str[j]时，dp[i][j] = max (dp[i][j-1], dp[i+1][j]]) 这是跟回文子串最不一样的地方，回文子串是不判断i位和j位不相等的情况的

7. 打家劫舍

给定一个数组例如 [1, 5, 4]，每项表示每个房间的钱币数量，不能偷相邻房间的钱，问最多能偷多少钱

• dp[i]表示前i位范围的房间内最多能偷多少钱
• 当第i个房间确定要偷时，它的前一个房间就不能偷，dp[i] = money[i] + dp[i-2]
• 当不偷第i个房间时：dp[i] = dp[i-1]
• 最终：dp[i] = max(money[i] + dp[i-2], dp[i-1])

升级版：

将第一个房间和最后一个房间连在一起，形成环，其他条件不变

image.png