记忆递归调用时效率差异巨大

Question

在做这个LeetCode问题时，我注意到有很大的不同性能取决于我决定编码的版本（请参阅注释的部分）。其中之一更简洁，但我看不出有什么区别。如有解释，将不胜感激。

class Solution:
    
    def rec_memo(self, nums, index, curr_sum, target, memo):

        if curr_sum == target:
            return True
        elif curr_sum > target or index == len(nums):
            return False
        
        if (index, curr_sum) in memo:
            return memo[(index, curr_sum)]

# This line (below) is significantly more efficient   

#         memo[(index, curr_sum)] = self.rec_memo(nums, index + 1, curr_sum + nums[index], target, memo) or self.rec_memo(nums, index + 1, curr_sum, target, memo)

# These lines (below) are significantly less efficient

#         choose_num = self.rec_memo(nums, index + 1, curr_sum + nums[index], target, memo)
#         not_choose_num = self.rec_memo(nums, index + 1, curr_sum, target, memo)
        
#         memo[(index, curr_sum)] = choose_num or not_choose_num
        
        return memo[(index, curr_sum)]
        
        
    def canPartition(self, nums: List[int]) -> bool:
        
        sum = 0
        for i in range(0, len(nums), 1):
            sum += nums[i]

        if sum % 2 != 0:
            return False
        
        memo = {}
        return self.rec_memo(nums, 0, 0, sum // 2, memo)
        

Answer 1

第一个：

self.rec_memo(nums, index + 1, curr_sum + nums[index], target, memo) or \
self.rec_memo(nums, index + 1, curr_sum, target, memo)

如果第一个返回 True，则不会评估后一个对 self.rec_memo() 的调用，因为 短路评估。

但是，对于第二个：

choose_num = self.rec_memo(nums, index + 1, curr_sum + nums[index], target, memo)
not_choose_num = self.rec_memo(nums, index + 1, curr_sum, target, memo)
memo[(index, curr_sum)] = choose_num or not_choose_num

无论第一次调用 rec_memo() 的结果如何，您都将始终进行第二次递归调用。您观察到的速度减慢可能是这些额外的递归调用的结果。