如何在具有两个状态变量的迭代系统中递归计算到达终止状态的所有路径？

Question

使用递归计算到达最终状态（A = 1）的方法数。

考虑一个具有两个状态变量 A 和 B 的迭代系统。

• A 的值为 0 或 1

• B 的值为 0,1,2,3 或 4

变量初始化为 (A,B) = (0,2)。在每次迭代中，两个状态变量之一可以转换为一个相邻的允许值，即对于 A 0 --> 1、1-->0。对于 B，值 2 可以转换为 2-->1 或 2-->3。
A=1 时达到最终状态。

在最大迭代次数后达到最终状态有多少种不同的方法？我应该编写一个递归计算这个数字的方法！

示例（A初始位置，B初始位置，当前步长，最大步长）=（0,2,0,1）= 1

这是我的尝试：

def recurse(A, B, step, max_step):
    if A == 1:
        return 1
    if step > max_step:
        return 0
    ways = 0
    if A == 0:
        ways += recurse(1, B, step + 1, max_step)
    if B > 0:
        ways += recurse(A, B - 1, step + 1, max_step)
    if B < 4:
        ways += recurse(A, B + 1, step + 1, max_step)
    return ways

但是从这个表中可以看出，它失败了：

输入	预期产出	实际产量
(0,2,0,1)	1	1
(0,2,0,2)	2	3
(0,2,0,3)	4	7

Answer 1

我发现你的功能有一些问题：

1. 寻找有效路径的方法是不完整的，当前步长必须等于最大步长
2. if 语句的错误使用，您应该使用 elif 以避免过度计算 ways 变量

该函数应如下所示：

def recurse(A, B, step, max_step):
    if (A == 1) and (step == max_step): 
        return 1   # valid path
    if step > max_step:
        return 0   # invalid path

    ways = 0
    # A transitions
    if A == 0:
        ways += recurse(1, B, step + 1, max_step)
    elif A == 1:
        ways += recurse(0, B, step + 1, max_step)

    # B transitions
    if B > 0:
        ways += recurse(A, B - 1, step + 1, max_step)
    elif B < 4:
        ways += recurse(A, B + 1, step + 1, max_step)
    return ways