[算法]动态规划-多维

已打卡题题目

:::warning 逆向

• 概率
• 688. 骑士在棋盘上的概率
• 837. 新 21 点

多维

• 62. 不同路径 :::

基础

312. 戳气球

经典LCS：

5. 最长回文子串

⚠️ 1. 边界

1. 先左下角按照列填写， 其余再按照行填写

🌰 “babad”

[
  [ null, false, true, false, false ], // [0, 2] bab
  [ null, null, false, true, false ],  // [1, 3] bab
  [ null, null, null, false, false ],
  [ null, null, null, null, false ],
  [ null, null, null, null, null ]
]

var longestPalindrome = function(s) {
    // [i, j]子串下标
    // dp[i][j] = dp[i+1][j-1] ^ s[i] === s[j]
    // 边界 (j-1) - (i+1) + 1< 2
    // 初始化， 单个字符是回文子串， dp[i][i] = true
    let len = s.length;
    let startIndex = 0;
    let maxLen = 1;
    let dp = Array.from({length: len}, v => new Array(len).fill(null));
    for (let j = 0; j < len; j++) {
        for (let i = 0; i < j; i++) {
            if (s.charAt(i) != s.charAt(j)) {
                dp[i][j] = false;
            } else {
                dp[i][j] = j - i < 3 ? true : dp[i+1][j-1];

            }
            // change max
            if (dp[i][j] && j - i + 1 > maxLen) {
                maxLen = j - i +1;
                startIndex = i;
            }
        }
    }
    return s.substring(startIndex, startIndex + maxLen);
};

1143. 最长公共子序列

给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列的长度。

一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。
例如，”ace” 是 “abcde” 的子序列，但 “aec” 不是 “abcde” 的子序列。两个字符串的「公共子序列」是这两个字符串所共同拥有的子序列。

若这两个字符串没有公共子序列，则返回 0。

输入：text1 = “abcde”, text2 = “ace”
输出：3
解释：最长公共子序列是 “ace”，它的长度为 3。

动态转移方程

1. 当text1[m] === text2[n]时，说明 text1[m] 或者 text2[n] 对应的字符是最长公共子序列的一部分，所以有 dp[m][n] = 1 + dp[m-1][n-1]
2. 当text1[m] !== text2[n]时，此时我们要看两个字符串分别单独往回撤一个字符串的对比情况，获取两者的最大值即可，所以有 dp[m][n] = Math.max(dp[m - 1][n], dp[m][n - 1], dp[m-1][n-1])

var longestCommonSubsequence = function(text1, text2) {
    // m行n列
    let m = text1.length, n = text2.length;
    let dp = Array.from({length: m+1}, v => new Array(n+1).fill(0));
    for (let i=0; i<m; i++) {
        for (let j=0; j<n; j++) {
            let s1 = text1.charAt(i), s2 = text2.charAt(j);
            if (s1 == s2) {
                dp[i+1][j+1] = 1 + dp[i][j];
            } else {
                dp[i+1][j+1] = Math.max(dp[i][j+1], dp[i+1][j], dp[i][j])
            }
        }
    }
    return dp[m][n]
};

公共子串计算（同上， 区别： 删除部分前缀和后缀）

给定两个只包含小写字母的字符串，计算两个字符串的最大公共子串的长度。
注：子串的定义指一个字符串删掉其部分前缀和后缀（也可以不删）后形成的字符串。

function LCS(str1, str2) {
    let m = str1.length, n = str2.length;
    let maxLen = 0;
    let dp = Array.from({length: m+1}, v => new Array(n+1).fill(0));
    for (let i=0; i < m; i++) {
        for (let j=0; j < n; j++) {
            if (str1.charAt(i) == str2.charAt(j)) {
                dp[i+1][j+1] = 1 + dp[i][j];
                maxLen = Math.max(maxLen, dp[i+1][j+1]);
            } else {
                dp[i+1][j+1] = 0
            }
        }
    }
    return maxLen;
}

1092. 最短公共超序列

练习：

剑指 Offer 47. 礼物的最大价值

当前上一步：左侧/上方
dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]) + grid[i][j]

var maxValue = function(grid) {
    let m = grid.length;
    let n = grid[0].length;
    let dp = Array.from({ length: m}, (a, i) => {
        return Array.from({ length: n}, (b, j) => {
            return i == 0 || j == 0 ? grid[i][j] : null
        })
    })
    for (let i = 1; i < m; i++) {
        dp[i][0] += dp[i-1][0]
    }
    for (let j = 1; j < n; j++) {
        dp[0][j] += dp[0][j-1]
    }
    // console.log(dp)
    for (let i = 1; i < m; i++) {
        for (let j = 1; j < n; j++) {
            dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]) + grid[i][j];
        }
    }
    // console.log(dp)
    return dp[m-1][n-1];
};

剑指 Offer 19. 正则表达式匹配

var isMatch = function(s, p) {
    let m = p.length;
    let n = s.length;
    let dp = Array.from({ length: m + 1 }, () => 
        new Array(n + 1).fill(false)
    )
    dp[0][0] = true;
    for (let i = 1; i < m; i++) {
        dp[i+1][0] = dp[i-1][0] && p[i] == '*'
    }
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (p[i] != '*') {
                // 是否相等 && 左上角
                dp[i+1][j+1] = dp[i][j] && (p[i] == s[j] || p[i] == '.')
            } else {
                // *匹配任意长度， 上方两格
                dp[i+1][j+1] = dp[i][j+1] || dp[i-1][j+1];
                if (p[i-1] == s[j] || p[i-1] == '.') {
                    dp[i+1][j+1] |= dp[i+1][j]
                }
            }
        }
    }
    // console.log(dp)
    return dp[m][n]
};

参考：https://www.bilibili.com/video/BV1Tt4y1U7QP?from=search&seid=15174622590668606460