野人与牧师过河的题目Python解决

这是一个经典的动态规划（Dynamic Programming, DP）问题，通常称为“野人与牧师过河”，也可以理解为背包问题的一个变种。Python通过创建一个二维数组或者列表来存储状态，并按照一定的规则递推求解。

以下是Python代码的一种实现方式：

def can_cross(wolves, priests, boat_size):
    # 初始化一个二维列表，记录每个时刻的状态
    dp = [[False] * (boat_size + 1) for _ in range(wolves + 1)]
    
    # 特殊情况，如果船是空的或者只有一个人需要过河，则可以过去
    dp[0][1] = True
    if wolves == 0:
        return [True]
    
    # 根据当前的狼和人的数量，尝试所有可能性
    for i in range(1, wolves + 1):
        for j in range(1, boat_size + 1):
            # 如果牧帝始终能过去，那么dp[i][j]就是dp[i - 1][j - 1]（没有狼的情况）
            dp[i][j] |= dp[i - 1][j]
            
            # 如果有狼，牧师需要先过河，然后狼再过，所以要看上一格是否可以，如果可以，再加上一个牧师
            if i > 1 and j >= 2:
                dp[i][j] |= dp[i - 2][j - 1]

    # 返回最终的结果
    return dp[wolves][boat_size]

# 测试数据
wolves = 3
priests = 2
boat_size = 4
result = can_cross(wolves, priests, boat_size)
print("牧师能否成功过河：", result[0])