爲什麼遞歸解決方案比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解決方案仍然更快。