91_Decode_Ways

Leetcode

思路

• 明显的可以拆分为小问题的求解"一共有多少"的String题目.
• 简单的想法就是: 尝试所有可能性 -> DFS. 但是DFS的时间复杂度高. 可以使用"记忆化DFS", 这样可以合并子树, 避免重复递归. 如同[leetcode] 91. Decode Ways 解题报告所说:
  

  只要是带记忆话搜索的, 大多都可以动归来解决.

DFS

1. 直接套用DFS模板

• 
  
  • 图解: 方框表示当前的暂存的结果, 标签(箭头)表示可以选择的input.
  • (s,2)表示的是当前的DFS的输入(只列出s和pos)
• dfs1(String s, List<Character> list, List<String> ans, Integer pos)
  
  • list: 即图中正方形, 用来保存DFS的每一个结果.
  • ans: 只保存DFS的最后的结果.
  • pos: 可选项的指针, 表示当前DFS使用哪一个elem.
• 这道题目中, 每次可以选择取下一位数, 拼到当前的list中. 或者可以选取下2位数, 拼到当前的list中.
  
  • eg. [1]<2,3]的时候, 可以分为:
    
    • 取1位, 即左路: [1,2]<3]
    • 取2位, 即右路: [1,23]<]
• DFS递归的退出条件: pos等于s的长度, 即选择完所有的数字. 从图中即叶子节点才讲list放入ans. 这相当于permutations的结束条件.

2. 改进DFS模板

• 这道题目只是要求一共有几种拆分方法. 所以不用存结果.
• dfs2(String s, List<Character> list, int[] ans, int pos)
• 只需要在上一个方法中, 在pos等于s的长度时, 增加ans即可.

3. 有返回值的DFS

• 对于要求一个结果(例如总共多少可能性)的DFS, 可以直接输出. 所以有了改进的DFS3.
• dfs3(String s, int pos)
• 即在分叉的时候, 把pick 1和pick 2的结果加起来作为输出.

4. 记忆化DFS (很关键的一个改进)

• 对于recursion, 总想着有没有可能合并分支, 从而加上一个mem来记录已经计算过的分支, 这样在别的分支发现已经计算过这种组合的话, 就直接从mem里面拿, 而不要recursion了.
• 这道题的关键是发现有重复的分支. 例如图中用曲线连起来的2个node: [1,2]<3]以及[12]<3]. 这两个可以写作: (s,2). 表示start是2的所有可能性. 因为这2个node, 都可以取下一位: 3. 所以这个node返回的结果是一样的.
• 而且要理解DFS中, 每一个node的入栈和出栈的. 参考Algs_DFS的previsit和postviist. 所以左边的(s,2)先计算, 放入map. 所以右边的(s,2)直接从map拿结果就行.
• 对于记忆化DFS, base case之前记得加上判断是否在map中有记录即可.

5. 更关键: DP

• DP是一种思想. DFS是一种实现. 而记忆化DFS就可以直接翻译成DP.
• 不过这个翻译也有catch:
  
  • top-down 还是 bottom-up?
    
    • 这里还是bottom-up直观些, 因为bottom-up类似recursion. 所以DP从后向前扫. 因为答案就是DP[0]
  • dp数列多大? 初始值多少?
    
    • plesae define dp array. 想想ZQ说的maximum sum的DP的一些拐弯的tips.
    • DP[i]表示从i到end的substring的拆分方法.
    • DP一般需要存多一个位, 表示边界情况, 因为DP[s.length()]一定等于1. 表示什么都不选的拆分方法是1. 其实就是记忆化DFS中的叶子节点: (s,3)
    • 还有一个边界情况是DP[s.length()-1], 在最后一个字符非0的时候, 有一个decode, 否则没有decode. 其实还可以DP[s.length()-2], 但这个其实可以直接在loop里面做, 因为挺多判断条件的.
  • for loop的时候, 实际从n-2开始, 因为n-1是边界情况. 想想有哪些需要讨论的: 00, 0x, 27-99. 可以用parseInt直接得到int. 所以要判断第一位是否为0, 若是, 则decode=0. 其次判断是否小于27. 于是有DP公式: $$dp[i] = (substr < 27) ? dp[i+1] + dp[i+2] : dp[i+1]$$ 我还想了一会这个i和i+1,i+2的关系是什么意思. 其实注意: 这是翻译记忆化DFS就好理解了, 就是父节点=2个子节点的和.