leetcode 91题 解码方法
题目地址：https://leetcode-cn.com/problems/decode-ways/
题目
一条包含字母 A-Z 的消息通过以下映射进行了 编码 ：
'A' -> 1
'B' -> 2
...
'Z' -> 26要 解码 已编码的消息，所有数字必须基于上述映射的方法，反向映射回字母（可能有多种方法）。例如，"11106" 可以映射为：
"AAJF"，将消息分组为(1 1 10 6)"KJF"，将消息分组为(11 10 6)
注意，消息不能分组为 (1 11 06) ，因为 "06" 不能映射为 "F" ，这是由于 "6" 和 "06" 在映射中并不等价。
给你一个只含数字的 非空 字符串 s ，请计算并返回 解码 方法的 总数。
题目数据保证答案肯定是一个 32 位 的整数。
示例 1：
输入： s = "12"
输出： 2
解释： 它可以解码为 "AB"（1 2）或者 "L"（12）。示例 2：
输入： s = "226"
输出： 3
解释： 它可以解码为 "BZ" (2 26), "VF" (22 6), 或者 "BBF" (2 2 6) 。示例 3：
输入： s = "0"
输出： 0
解释： 没有字符映射到以 0 开头的数字。
含有 0 的有效映射是 'J' -> "10" 和 'T'-> "20" 。
由于没有字符，因此没有有效的方法对此进行解码，因为所有数字都需要映射。示例 4：
输入： s = "06"
输出： 0
解释： "06" 不能映射到 "F" ，因为字符串含有前导 0（`"6"` 和 `"06"` 在映射中并不等价）。提示：
1 <= s.length <= 100s只包含数字，并且可能包含前导零。
要求
- 统计能解码(匹配)到的个数。
- 0 开头的数字不行。
- 映射的结果在26个字母范围之内。
- 这是一个斐波那契规律的字符串。
分析
开头为 0 直接返回 0。
0 是一个特殊的判断条件。
每一个匹配到的值必须小于等于26。
这是一个符合斐波那契数列规律的问题。
var numDecodings = function (s) {
const n = s.length;
// 如果 n === 0 或者 s[0] === '0'，直接结束，我喜欢使用includes
if (isZero(n) || isZero(s[0]) ) {
return 0
}
// 使用一个表来存取匹配到的数量
const dpTable = Array(n + 1).fill(0)
// 斐波那契
dpTable[0] = 1
dpTable[1] = 1
for (let i = 2; i <= n; i ++) {
// 情况一：倒数一位不为0
if (!isZero(s[i-1])) {
dpTable[i] = dpTable[i] + dpTable[i - 1];
}
// 情况二：倒数两位 大于等于 10 并且小于等于 26
const value =Number(dpTable[i - 2] + dpTable[i - 1])
if (value >= 10 && value <= 26) {
dpTable[i] = dpTable[i] + dpTable[i - 2];
}
}
return dpTable[n]
function isZero(num) {
return [0, '0'].includes(num)
}
}核心扩展
91题的题解使用到了动态规划，动态规划是很常见的算法设计技巧，同时这道题也使用到了斐波那契数列的规律，那我们就那斐波那契数列来举例吧。
层层递进的固定流程：递归的暴力解法 -> 带备忘录的递归解法 -> 非递归的动态规划解法
求斐波那契数列（递归的暴力解法）
function fibonacci (n) {
if ([1, 2].includes(n)) {
return 1
}
return fibonacci(n - 1) + fibonacci(n - 2)
}把这种暴力递归的解法画一张图出来：
是不是有重复的计算？像这样的二叉树的节点总数是指数级的，所以所有子问题的个数为 (n^2) 噢，这么做会导致时间复杂度爆炸，因为时间复杂度也变成了 O(n^2) 。
求斐波那契数列 （带备忘录的递归解法）
let dp = [1, 1]
function fibonacci (n) {
if (dp[n - 1]) {
return dp[n - 1]
}
dp[n - 1] = fibonacci(n - 1) + fibonacci(n - 2);
return dp[n - 1]
}这种带备忘录的递归解法是针对暴力递归的解法做的优化，优化的操作其实就是对那颗指数级的二叉树进行剪枝，剪枝会减少重复的树节点(减少了重复的计算)。
这种带备忘录的递归解法也画一张图出来：
红色实线部分圈着的是被剪枝的节点，是不是剪掉了所有的重复树节点？没错是的，所有重复的子问题都被干掉了，时间复杂度骤减。
没错，它时间复杂度也从O(n^2)降低到了O(n)，如果用空间去换时间的话，它的时间复杂度甚至还会从O(n) 降 O(1)。
惊叹算法设计的神奇。从O(n^2)到O(n)再到O(1)，速度一下子就上去了。
假设这个 n 为 1000，O(1000^2)、O(1000)、O(1) 这三者相比之下，可以体会到时间复杂度的提升是质的飞升。
求斐波那契数列 （非递归的动态规划解法）
function fibonacci (n) {
let dp = Array(n).fill(0);
dp[0] = dp[1] = 1;
for (let i = 2; i < n; i ++) {
dp[i] = dp[i-1] + dp[i - 2]
}
return dp[n - 1];
}无论是递归的暴力解法还是带备忘录的递归解法，实际上本质都是自顶向下(从上到下)，看上面两张图不难发现这个规律。
使用动态规划的方式，你可以看到我们是自底向上(从下往上)，也就是从最小的问题逐渐往上推，先求fibonacci(2)再求fibonacci(3)...最后fibonacci(20)。
递归是自顶向下，从上向下的延申，逐层分解问题的规模，直到触及到底部(小问题得以解决)，然后再逐层的向上返回答案，最后求出最大的那个问题的解。
动态规划一般都是非递归的，是自底向上的循环迭代，先解决最小规模的问题，再用小问题的答案求解除最大规模问题的解。
动态规划
从求斐波那契数列的非递归动态规划解法中，我可以分析到三个要素，这三个要素也是动态规划的显著特征。
- 状态转移方程：例如 dp[0] = dp[1] = 1;dp[i] = dp[i-1] + dp[i-2];
- 暴力解法：想到了这个状态转移方程后，就能写出这个暴力解的算法，比如使用 DP Table 和 for循环 来实现求斐波那契数列的算法 。
- 独立最优子结构：子问题必须相互独立，最大规模问题的解是由多个子问题的最优解计算得来的。
画一下这三个特征的图：
也许这张图不是很明显，那么可以换另一个更生动的方式来说明，比如leetcode 中 322.零钱兑换。
leetcode 322题 零钱兑换
给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。
你可以认为每种硬币的数量是无限的。
示例 1：
输入： coins = [1, 2, 5], amount = 11
输出： 3
解释： 11 = 5 + 5 + 1示例 2：
输入：coins = [2], amount = 3
输出：-1示例 3：
输入： coins = [1], amount = 0
输出： 0示例 4：
输入： coins = [1], amount = 1
输出： 1示例 5：
输入： coins = [1], amount = 2
输出： 2提示：
1 <= coins.length <= 121 <= coins[i] <= 231 - 10 <= amount <= 104
要求
- 有三种面额的金币：1元、2元、5元
- 用这三种面额的金币组合出指定的总额
- 这三种面额的金币支持重复组合
- 最少使用几枚可以组合出指定的总额
分析
总额为13，那么最少需要四张：5 + 5 + 2 + 1
总额为0 时，直接返回 0
每一次的解都在 coins中，下一次的因依赖与上一次的解，比如 第一次的解为5，下一次的因就是 13 - 5，那么剩下的解就是 从 8 中计算得出。
可以遍历coins，如果下一次的因小于 coins中某个金币面额，那么就continue一下，切换下一个面额。
累积计数，求最小值。
递归的写法
这种写法性能贼差嘞，递归中套循环，循环中有递归，复杂度是 O(n^count)，也就是n的每一轮循环的总次数的那么多次方噢，爆炸，如果coins中有五个元素，那么时间复杂度就是O(n^5)，爆炸了爆炸了。
var coinChange = function(coins, amount) {
if ([0, '0'].includes(amount)) {
return 0
}
let temp = Number.MAX_VALUE
for(let coin of coins) {
if (amount - coin < 0) continue;
const result = coinChange(coins, amount - coin);
if (result === -1) continue;
temp = Math.min(temp, result + 1);
}
return temp === Number.MAX_VALUE ? -1 : temp
};如图：
带备忘录的递归写法
这种写法对原来的递归树进行了剪枝操作，极大的减少了重复的运算。复杂度是O(n*count)，重复的问题都不会继续运算，时间复杂度是O(n)。
var coinChange = function(coins, amount) {
const memory = Array(amount).fill(-10);
return calcCoinChange(coins, amount)
function calcCoinChange(coins, amount) {
if ([0, '0'].includes(amount)) {
return 0
}
const curIndex = amount - 1
if (memory[curIndex] !== -10) {
return memory[curIndex];
}
let temp = Number.MAX_VALUE
for (let coin of coins) {
if(amount - coin < 0) continue;
const result = calcCoinChange(coins, amount - coin);
if (result === -1) continue;
temp = Math.min(temp, result + 1);
}
memory[curIndex] = temp === Number.MAX_VALUE ? -1 : temp;
return memory[curIndex]
}
};如图：
动态规划的写法
这种写法采用双重for循环加dp数组，也是自底向上的，动态规划是一种分阶段 求解 决策 的数学思想。下面这种写法的时间复杂度也是O(n)。
var coinChange = function(coins, amount) {
if ([0, '0'].includes(amount)) return 0
const dp = Array(amount + 1).fill(amount + 1)
dp[0] = 0
for (let i = 1; i <= amount; i ++)
for (const coin of coins)
if (coin <= i) {
dp[i] = Math.min(dp[i], dp[i - coin] + 1)
}
return dp[amount] > amount ? -1 : dp[amount]
}另类题解
通过正则表达式和求斐波那契数列的方式来实现91题
/**
* @param {string} s
* @return {number}
*/
var numDecodings = function(s) {
if(s[0] == '0') return 0;
if(/(30)|(40)|(50)|(60)|(70)|(80)|(90)|(00)/.test(s)) return 0;
list = s.match(/(1|2)*(1[03456789])|(1|2)*(2[03456])|(1|2)+/g);
if(list) {
let solve = 1, minus = 0;
for(let i=0; i<list.length; i++) {
minus = /0$/.test(list[i]) ? 2 : 0;
solve *= fb(list[i].length - minus);
}
return solve
} else return 1;
function fb(index) {
if(index <= 1) return 1;
var num1 = 1, num2 = 1, ans = 2;
for(let i=2; i<index; i++) {
num1 = num2;
num2 = ans;
ans = num1 + num2;
}
return ans;
}
};
