动态规划#

1 将数字翻译成字符串#

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

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

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

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

1
const findLength = (A, B) => {
2
    const m = A.length;
3
    const n = B.length;
4
    const dp = Array.from(Array(n+1),()=>Array(n+1).fill(0))
5
    let res = 0;
6
    for (let i = 1; i <= m; i++) {
7
        for (let j = 1; j <= n; j++) {
8
            if (A[i - 1] == B[j - 1]) {
9
            dp[i][j] = dp[i - 1][j - 1] + 1;
10
            }
11
            res = Math.max(dp[i][j], res);
12
        }
13
    }
14
    return res;
15
}

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]

1
var isInterleave = function(s1, s2, s3) {
2
    let n1 = s1.length
3
    let n2 = s2.length
4
    let n3 = s3.length
5
    if(n1+n2 !== n3){
6
        return false
7
    }
8

9
    let f = new Array(n2+1)
10
    for(let i=0;i<n2+1;i++){
11
        f[i] = []
12
    }
13
    f[0][0] = true
14

15
    for(let i=0;i<n2+1;i++){
16
        for(let j=0;j<n1+1;j++){
17
            let p = i+j-1
18
            if(i>0){
19
                f[i][j] |= f[i-1][j] && s2[i-1] === s3[p]
20
            }
21
            if(j>0){
22
                f[i][j] |= f[i][j-1] && s1[j-1] === s3[p]
23
            }
24
        }
25
    }
26
    return f[n2][n1]
27
}