为什么递归解决方案比DP解决方案有更复杂的基础案例？

Question

我正在研究算法问题，以查找将整数解码为字符串的方法数量。我制定了一个DP解决方案和递归解决方案。

递归解决方案似乎有一个更复杂的基本情况。我试图理解为什么会这样，如果它是一个模式，或者如果我在编写递归基础案例时真的很糟糕。

DP解决方案：

# @param {String} s 
# @return {Integer} 
def num_decodings(s) 
    return 0 if s.length == 0 
    n = s.length 
    memo = Array.new(n+1,0) 
    memo[n] = 1 
    memo[n-1] = s[n-1]=="0" ? 0 : 1 
    (0...n-1).to_a.reverse.each do |i| 
    next if s[i] == "0" 
    memo[i] = s[i...(i+2)].to_i <= 26 ? memo[i+1] + memo[i+2] : memo[i+1] 
    end 
    puts memo.to_s 
    return memo[0] 
end 

递归解决方案：

# @param {String} s 
# @return {Integer} 
def num_decodings(s) 
    #puts "s: #{s}" 
    return 0 if s.length == 0 
    return 0 if s[0] == "0" 
    return 1 if s.length == 1 
    return 1 if s.length == 2 && s[1] == "0" && s.to_i <= 26 
    return 0 if s.length == 2 && s[1] == "0" && s.to_i > 26 
    return 2 if s.length == 2 && s.to_i <= 26 
    return 1 if s.length == 2 
    @ways ||= {} 
    return @ways[s] if @ways[s] 
    if s[0..1].to_i <= 26 
     @ways[s] = num_decodings(s[1..-1]) + num_decodings(s[2..-1]) 
    else 
     @ways[s] = num_decodings(s[1..-1]) 
    end 
    #puts @ways 
    return @ways[s] 
end 

输入："2" 输出：2

这是对本文给出了这样的问题：https://leetcode.com/problems/decode-ways/

Answer 1

我继续在递归解决方案上工作，并意识到虽然DP解决方案只需要解决n-1和n-2问题，但我的递归基础案例恰巧是不必要的奇怪。所以我简化它，并结束了与此：

def num_decodings(s) 
    return 0 if s.length == 0 
    return 0 if s[0] == "0" 
    return 1 if s.length == 1 
    @ways ||= {} 
    return @ways[s] if @ways[s] 
    if s[0..1].to_i <= 26 
     prev = s.length <= 2 ? 1 : num_decodings(s[2..-1]) 
     @ways[s] = num_decodings(s[1..-1]) + prev 
    else 
     @ways[s] = num_decodings(s[1..-1]) 
    end 
    return @ways[s] 
end 

该解决方案已经非常相似，DP解决方案，是在一个类似的复杂度。

当然，DP解决方案仍然更快。