题意理解

  • 数组中的所有数字都必须参与译码，并且数字范围是[1, 26]。
  • 两位数组合应该在[10, 26]之间，并且是十位数，如02的组合也是无效的。
  • 0作为单数字译码肯定是无效的，0和其他数字组合作为译码时，只有10和20这个组合可以在[10, 26]范围内译码，其他情况都是无效的，此时这个数组就无法译码，译码方式为0。
  • 当新加入一个数字时，这个数字可以作为单数字译码，也可以和左边的数字组合后再译码，但这两种译码方式都必须满足[1, 26]范围。

最小子问题

  • 当数组中只有一个数字时，只有一种译码方式，但要保证这个数字不是0，此时dp[0]=1。
  • 其他所有位置的初始译码方式都为0，这是为了考虑数字中含有0的情况。

如何思考状态转移方程？

  • 当前位置如果作为单数字译码，则和前面一位数字作为末尾的译码方式一样，此时dp[i] = dp[i-1]
  • 当前位置如果和前面一位数字作为组合译码，则译码方式还应该加上前面两位数字作为末尾的方式，因此dp[i] += dp[i-2]

状态转移方程的推导过程

https://blog.nowcoder.net/n/6e9d8904d9fe44808c1474e4ea4d2583

/**
 * 解码
 * @param nums string字符串 数字串
 * @return int整型
 */
function solve( nums ) {
    // write code here
    const dp = new Array(nums.length).fill(0);
    

    if (!nums.startsWith("0")) {  // 有可能只传入一个0，也有可能传入开头为0的字符串
        dp[0] = 1;
    }

    for (let i = 1; i < nums.length; ++i) {
        if (nums[i] !== "0") {  // 当前位置作为单数字译码，只需要求当前数字不为0，为0的话当前位置有0种译码方式
            dp[i] == dp[i-1];
        }
        // if (nums[i] === "0") {
        //     if (nums[i-1] !== "1" && nums[i-1] !== "2")
        //         return 0;
        // }
        const tempNum = Number(nums[i-1]+nums[i]);
        if (tempNum >=10 && tempNum <= 26) {  // 当前位置作为组合数字译码，数字范围要在10到26，如果前面位置是0，当前位置也是0，同样不满足当前情况，当前位置有0种译码方式
            i === 1 ? dp[i] += 1 : dp[i] += dp[i-2];  // 要考虑只有i=1时只有两个数字的情况
        }  // 如果字符串是1001，00组合无效，最后的0位置的译码方式为0，01组合也无效，最后1位置的译码方式等于前面0的译码方式，即0
    }

    return dp[nums.length - 1];
}
module.exports = {
    solve : solve
};