狼羊菜渡河问题python

狼羊菜渡河问题是源于计算机科学的一个经典动态规划问题，也称为“猎人、兔子和白菜”的变体。在这个问题中，有三个人和一条小船，他们需要一起过河，但每次只能带一个人或一样东西过河。规则是：

1. 狼不吃兔子，兔子不吃菜，狼不吃菜。
2. 当单独留下狼或兔子时，它们会互相攻击。

目标是最优地安排渡河顺序，使得所有人都能安全到达对岸。可以用Python编写递归或迭代的方式来解决这个问题，通常涉及创建状态转移表或动态规划数组。

下面是一个简单的Python迭代解决方案：

def wolf_rabbit_cabbage(is_wolf_on_left=False, is_rabbit_on_left=False):
    dp = {0: (is_wolf_on_left, is_rabbit_on_left)} # 初始化，表示空船状态
    for i in range(1, 4): # 从1到3，代表狼、兔、菜分别上船
        wolf_left, rabbit_left = dp[i - 1]
        dp[i] = (
            wolf_left and not rabbit_left,  # 狼独在，可以带兔
            rabbit_left and not wolf_left,  # 兔独在，可以带菜
            wolf_left and rabbit_left,      # 都在，先让兔走
            not wolf_left and not rabbit_left  # 都不在，随便选
        )
    
    return dp[3]

# 调用函数获取最终的渡河方案
solution = wolf_rabbit_cabbage()