再帰的ソリューションは、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" 出力：https://leetcode.com/problems/decode-ways/

Answer 1

私は続けた：2

それはLeetcodeでこの問題があります再帰的な解法に取り組んで、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ソリューションはまだまだ高速です。