动态规划解决2xN网格最大路径和问题

def max_path_sum_initial(A, B):
    N = len(A)
    # dp[0][i] 存储到达 A[i] 的最大和
    # dp[1][i] 存储到达 B[i] 的最大和
    dp = [[0 for _ in range(N)] for _ in range(2)]

    # 基线条件
    dp[0][0] = A[0]

    # 计算第一行 A 的路径和
    for i in range(1, N):
        dp[0][i] = dp[0][i - 1] + A[i]

    # 计算 B[0] 的路径和 (注意这里在原始代码中被放在了循环内，是不必要的重复计算)
    # dp[1][0] = dp[0][0] + B[0]

    # 计算第二行 B 的路径和
    # 原始代码中的 B[0] 计算在这里
    for i in range(N): # 循环从0开始以包含 B[0] 的计算
        if i == 0:
            dp[1][0] = dp[0][0] + B[0] # 第一次迭代计算 B[0]
        else:
            dp[1][i] = max(dp[1][i - 1] + B[i], dp[0][i] + B[i])

    return dp[1][N - 1]

# 示例测试
# A = [1, 2, 3]
# B = [4, 5, 6]
# print(max_path_sum_initial(A, B)) # 期望输出: 1+2+3+6 = 12 或 1+4+5+6 = 16
# 1 -> 2 -> 3 -> (down) -> 6 = 12
# 1 -> 2 -> (down) -> 5 -> 6 = 14
# 1 -> (down) -> 4 -> 5 -> 6 = 16

def max_path_sum_optimized(A, B):
    N = len(A)
    if N == 0:
        return 0 # 处理空数组情况

    dp = [[0 for _ in range(N)] for _ in range(2)]

    # 基线条件：计算 dp[0][0] 和 dp[1][0]
    dp[0][0] = A[0]
    dp[1][0] = dp[0][0] + B[0] # 优化点1：提前计算 dp[1][0]

    # 合并循环，计算 dp[0][i] 和 dp[1][i]
    for i in range(1, N): # 优化点2：合并循环
        dp[0][i] = dp[0][i - 1] + A[i]
        dp[1][i] = max(dp[1][i - 1] + B[i], dp[0][i] + B[i])

    return dp[1][N - 1]

# 示例测试
A_test = [1, 2, 3]
B_test = [4, 5, 6]
print(f"优化后函数计算结果: {max_path_sum_optimized(A_test, B_test)}") # 期望输出: 16

A_test2 = [10, -5, 20]
B_test2 = [1, 10, 5]
print(f"优化后函数计算结果2: {max_path_sum_optimized(A_test2, B_test2)}")
# Path 1: A[0]->A[1]->A[2]->B[2] = 10 + (-5) + 20 + 5 = 30
# Path 2: A[0]->A[1]->B[1]->B[2] = 10 + (-5) + 10 + 5 = 20
# Path 3: A[0]->B[0]->B[1]->B[2] = 10 + 1 + 10 + 5 = 26
# Max is 30

def max_path_sum_space_optimized(A, B):
    N = len(A)
    if N == 0:
        return 0

    # 使用两个变量存储前一个位置的最大和
    # current_a_sum 对应 dp[0][i-1]
    # current_b_sum 对应 dp[1][i-1]

    # 初始化基线条件
    prev_a_sum = A[0]
    prev_b_sum = prev_a_sum + B[0]

    for i in range(1, N):
        # 计算当前 A[i] 的最大和
        current_a_sum = prev_a_sum + A[i]

        # 计算当前 B[i] 的最大和
        # 它可以从 B[i-1] 过来，或者从 A[i] 向下过来
        current_b_sum = max(prev_b_sum + B[i], current_a_sum + B[i])

        # 更新 prev_a_sum 和 prev_b_sum 为当前值，为下一次迭代做准备
        prev_a_sum = current_a_sum
        prev_b_sum = current_b_sum

    return prev_b_sum

# 示例测试
A_test = [1, 2, 3]
B_test = [4, 5, 6]
print(f"空间优化后函数计算结果: {max_path_sum_space_optimized(A_test, B_test)}") # 期望输出: 16