如何用动态规划求解Alice慢跑N米的不同行进方式数量？

状态定义 #

我们定义dp[i]为走完i米的所有不同行进方式总数。

状态转移逻辑 #

要到达i米的位置，最后一步只有两种可能：

• 最后一步是步行1米，那前面走完i-1米的所有方式都适用，对应dp[i-1]种
• 最后一步是跑步2米，那前面走完i-2米的所有方式都适用，对应dp[i-2]种
  所以状态转移方程为：dp[i] = dp[i-1] + dp[i-2]

边界条件 #

• dp[0] = 1：0米的距离只有1种方式（原地不动）
• dp[1] = 1：1米的距离只有步行1米这1种方式

我们可以直接用给出的示例验证逻辑正确性：

• 当n=3时，dp[3] = dp[2]+dp[1] = (dp[1]+dp[0]) + dp[1] = 2+1=3，和示例1输出一致
• 当n=4时，dp[4] = dp[3]+dp[2] =3+2=5，和示例2输出一致

基础DP版本（空间复杂度O(n)） #

n = int(input())
if n <= 1:
    print(1)
else:
    dp = [0]*(n+1)
    dp[0] = 1
    dp[1] = 1
    for i in range(2, n+1):
        dp[i] = dp[i-1] + dp[i-2]
    print(dp[n])

空间优化版本（空间复杂度O(1)） #

因为计算dp[i]只需要前两个状态的值，不需要存储整个状态数组，只用两个变量存前两个值即可：

n = int(input())
a, b = 1, 1
for _ in range(2, n+1):
    a, b = b, a + b
print(b)

你原来的排列枚举方案需要生成所有排列并去重，时间复杂度是指数级的，n超过20之后运行速度就会明显变慢。动态规划方案时间复杂度为O(n)，即使n到10^6也能快速计算，优化后的版本空间复杂度只有O(1)，效率提升非常明显。

内容的提问来源于stack exchange，提问作者hinok32