动态规划

1 将数字翻译成字符串

给定一个数字，我们按照如下规则把它翻译为字符串：0 翻译成 “a” ，1 翻译成 “b”，……，11 翻译成 “l”，……，25 翻译成 “z”。一个数字可能有多个翻译。请编程实现一个函数，用来计算一个数字有多少种不同的翻译方法。

输入: 12258
输出: 5
解释: 12258有5种不同的翻译，分别是”bccfi”, “bwfi”, “bczi”, “mcfi”和”mzi”

// 主要就是判断最后两个数字是否在10-25之间
var translateNum = function(num) {
    var num_str = num.toString()
    var n = num_str.length
    var d = [1]
    d[-1] = 1
    for(let i=1;i<n;i++){
        let dig = +num_str.substr(i-1,2)
        if(dig >= 10 && dig <=25){
            d[i] = d[i-1] + d[i-2]
        }else{
            d[i] = d[i-1]
        }
    }
    return d[n-1]
}

2 最长重复子数组

给两个整数数组 A 和 B ，返回两个数组中公共的、长度最长的子数组的长度。

输入:
A: [1,2,3,2,1]
B: [3,2,1,4,7]
输出: 3
解释: 长度最长的公共子数组是 [3, 2, 1]

状态转移方程 dp[i][j] = dp[i-1][j-1] + 1

const findLength = (A, B) => {
    const m = A.length;
    const n = B.length;
    const dp = Array.from(Array(n+1),()=>Array(n+1).fill(0))
    let res = 0;
    for (let i = 1; i <= m; i++) {
        for (let j = 1; j <= n; j++) {
            if (A[i - 1] == B[j - 1]) {
            dp[i][j] = dp[i - 1][j - 1] + 1;
            }
            res = Math.max(dp[i][j], res);
        }
    }
    return res;
}

3 交错字符串

给定三个字符串 s1, s2, s3, 验证 s3 是否是由 s1 和 s2 交错组成的。

输入: s1 = “aabcc”, s2 = “dbbca”, s3 = “aadbbcbcac”
输出: true

输入: s1 = “aabcc”, s2 = “dbbca”, s3 = “aadbbbaccc”
输出: false

f[i][j] |= f[i-1][j] && s2[i-1] === s3[p]

var isInterleave = function(s1, s2, s3) {
    let n1 = s1.length
    let n2 = s2.length
    let n3 = s3.length
    if(n1+n2 !== n3){
        return false
    }

    let f = new Array(n2+1)
    for(let i=0;i<n2+1;i++){
        f[i] = []
    }
    f[0][0] = true

    for(let i=0;i<n2+1;i++){
        for(let j=0;j<n1+1;j++){
            let p = i+j-1
            if(i>0){
                f[i][j] |= f[i-1][j] && s2[i-1] === s3[p]
            }
            if(j>0){
                f[i][j] |= f[i][j-1] && s1[j-1] === s3[p]
            }
        }
    }
    return f[n2][n1]
}