圆环回原点问题 #

问题描述 #

圆环上有10个点，编号为0~9。从0点出发，每次可以逆时针和顺时针走一步，问走n步回到0点共有多少种走法。

解答（动态规划） #

这是一个经典的动态规划问题，可以用斐波那契数列的思想来解决。因为圆环上有10个点，所以每次移动实际上是对10取模的操作。从0点出发，逆时针走一步到1，顺时针走一步到9，所以问题可以转化为在模10的情况下，走n步回到0点的走法数量。 定义两个数组，dp1 和 dp2，其中 dp1[i] 表示从0点出发，走i步后回到0点的走法数量，dp2[i] 表示从0点出发，走i步后不在0点的走法数量。 初始状态：

• dp1[0] = 1，因为从0点出发不走，就是回到0点。
• dp1[1] = 0，因为走一步不可能回到0点。
• dp2[0] = 0，因为不走就不可能不在0点。
• dp2[1] = 2，因为可以走到1或者9。 状态转移方程：
• dp1[i] = dp2[i - 1]，因为最后一步必须是从1或9走回0。
• dp2[i] = dp2[i - 1] * 2 - dp1[i - 1]，因为最后一步可以是从1或9走到另一个点，也可以是从其他点走回0。 最终答案是 dp1[n]。 现在，我们可以用Python代码来实现这个动态规划算法。

def count_ways(n):
    # 圆环上的点数
    points = 10
    # 初始化dp1和dp2
    dp1 = [0] *(n + 1)
    dp2 = [0] * (n + 1)
    # 设置初始状态
    dp1[0] = 1
    dp2[1] = 2
    # 动态规划填表
    for i in range(2, n + 1):
        dp1[i] = dp2[i - 1]
        dp2[i] = dp2[i - 1] * 2 - dp1[i - 1]
    # 返回走n步回到0点的走法数量
    return dp1[n]

详解 #

代码中使用的动态规划（DP）方法是为了解决在圆环上走n步回到起点0的总走法数量问题。这里使用了两个DP数组（dp1和dp2）来存储中间结果，它们的含义如下：

• dp1[i]表示走i步回到起点0的走法数量。
• dp2[i]表示走i步到达圆环上任意一点的走法数量。

关键在于理解dp2的更新逻辑：dp2[i] = dp2[i - 1] * 2 - dp1[i - 1]。这里，dp2[i - 1] * 2表示从前一步（第i-1步）到达任意点的走法数量乘以2（因为每一步都可以选择顺时针或逆时针走），然后减去dp1[i - 1]（即走i-1步回到起点的走法数量），因为这些走法在第i步不能再次回到起点，所以要排除。

假设(n=5)，我们来填写DP表格：

解释每一步的计算过程：

• 当(i=0)时，不移动自然是唯一的方法回到起点，所以dp1[0]=1；而dp2[0]不适用于任何场景，因为至少需要走一步。
• 当(i=1)时，从0出发只能到达1或9，所以无法回到0，dp1[1]=0；到达任意点的方法有2种，所以dp2[1]=2。
• 当(i=2)时，从1或9出发，只有两种方式回到0（逆时针或顺时针），所以dp1[2]=2；而到达任意点的方法是前一步的两倍减去回到0点的方法数，即dp2[2]=2*2-0=4。
• 当(i=3)时，从任意点出发，回到0的方法是上一步到达任意点的方法数，即dp1[3]=dp2[2]=4；到达任意点的方法数则是dp2[3]=dp2[2]*2-dp1[2]=4*2-2=6。
• 当(i=4)时，dp1[4]=dp2[3]=6；dp2[4]=dp2[3]*2-dp1[3]=6*2-4=8。
• 当(i=5)时，dp1[5]=dp2[4]=8；dp2[5]=dp2[4]*2-dp1[4]=8*2-6=10。

注意：在解释中，有一处计算修正需要注意，特别是对于dp2[i]的更新。正确的计算应该遵循dp2[i] = dp2[i - 1] * 2 - dp1[i - 1]，但在填写表格时，直接用了结果值而未详细解释每一步的具体计算，特别是对于dp2[2]和之后的计算。应更准确地追踪每一步的计算，以确保逻辑的准确性。例如，对于i=2的情况，正确的解释应该是考虑到从任意一点出发有两种选择（顺时针或逆时针），并且需要从dp2[i-1]准确计算出dp2[i]，同时考虑到dp1[i]是基于dp2[i-1]的值。