Python实现打家劫舍代码报错TypeError:int和str无法执行+运算

学习Python过程中实现打家劫舍算法时遇到运行异常，算法需求为：给定各房屋存放金额，相邻房屋不能同时被盗，求可盗取的最大金额，本次使用的测试数据为6,7,1,30,8,2,4。
原始实现代码如下：

# Given N, Amount of money in the house. Adjacent houses can't be stolen. Find the max amount that can be stolen
# 6,7,1,30,8,2,4
numbers = input()
n = numbers.split(",")
t = numbers.count(",")
def rob(nums, i):
    if i <= 0:
        return 0
    return max(rob(nums, i-2) + nums[i], rob(nums, i-1))
print(rob(n, t))

运行程序输入测试数据后，返回如下类型错误：

TypeError: unsupported operand type(s) for +: 'int' and 'str'

一共存在两个问题，其中第一个问题直接触发上述报错：

• 类型转换缺失：使用split(",")切割输入字符串得到的列表元素全是字符串类型，没有转为整数，执行加法运算时，递归返回的整数和字符串类型的房屋金额无法相加，触发类型错误。
• 递归边界逻辑错误：终止条件设置为i <= 0时返回0，会导致索引为0的第一个房屋的金额永远无法被计入计算，即使修复类型问题，最终计算结果也会出错。

1. 对切割后的输入列表做整数类型转换
2. 修正递归终止条件为i < 0时返回0，覆盖负索引的边界场景，保证第一个房屋的金额能被正常计算
3. （可选优化）原始递归写法存在大量重复计算，数据量大时会超时，可以加记忆化缓存提升运行效率

修复后可正常运行的基础版代码如下：

numbers = input()
# 切割后直接转整数列表
n = [int(num) for num in numbers.split(",")]
t = len(n) - 1 # 直接取列表长度减1作为起始索引，和统计逗号数量的结果等价，可读性更好

def rob(nums, i):
    # 修正边界条件：索引小于0时返回0
    if i < 0:
        return 0
    return max(rob(nums, i-2) + nums[i], rob(nums, i-1))

print(rob(n, t))

运行输入6,7,1,30,8,2,4时，会正确输出结果41。

如果需要优化递归效率，可以使用记忆化装饰器缓存中间结果，修改方式如下：

from functools import lru_cache

numbers = input()
n = [int(num) for num in numbers.split(",")]

@lru_cache(maxsize=None)
def rob(i):
    if i < 0:
        return 0
    return max(rob(i-2) + n[i], rob(i-1))

print(rob(len(n)-1))

内容的提问来源于stack exchange，提问作者Lemon