从棋盘到代码：用Python 3.10+轻松搞定‘移动路线’动态规划（附OpenJudge真题解析）

想象一下国际象棋中的车（Rook），它只能沿着直线移动。现在给你一个m×n的棋盘，问你从左上角(1,1)移动到右下角(m,n)有多少种不同的路径？这就是经典的"移动路线"问题，也是理解动态规划（Dynamic Programming）的绝佳入门案例。

对于信息学奥赛（NOI）和OpenJudge的参赛者来说，动态规划往往是区分选手水平的关键技能。但很多初学者在面对dp[i][j]这样的状态表示时，常常感到困惑不解。本文将用最直观的棋盘类比，带你从零开始理解这个问题的三种Python解法，并深入分析边界条件的处理技巧——这些正是竞赛中容易失分的"魔鬼细节"。

1. 动态规划与棋盘行走的直观映射

动态规划之所以让初学者望而生畏，很大程度上是因为其抽象的状态转移方程。但如果我们把它具象化为棋盘上的移动，一切就变得清晰起来。

以5×5的棋盘为例，我们需要计算从(1,1)到(5,5)的所有可能路径数。根据规则，每次只能向右或向下移动一格。这就意味着：

• 到达某个格子(i,j)的路径数 = 从上方格子(i-1,j)来的路径数 + 从左方格子(i,j-1)来的路径数

这正是动态规划中的 状态转移方程 ： dp[i][j] = dp[i-1][j] + dp[i][j-1]

边界条件 的特殊处理：

• 第一行的格子只能从左方来（因为上方没有格子）
• 第一列的格子只能从上方来（因为左方没有格子）
• 起点(1,1)的路径数为1（不动也算一种路径）

# 基础递推解法框架
def count_paths(m, n):
    dp = [[0]*(n+1) for _ in range(m+1)]  # 创建(m+1)×(n+1)的二维数组
    dp[1][1] = 1  # 初始条件
    
    for i in range(1, m+1):
        for j in range(1, n+1):
            if i == 1 and j == 1:
                continue
            if i == 1:  # 第一行
                dp[i][j] = dp[i][j-1]
            elif j == 1:  # 第一列
                dp[i][j] = dp[i-1][j]
            else:  # 其他情况
                dp[i][j] = dp[i-1][j] + dp[i][j-1]
    
    return dp[m][n]

注意：在竞赛编程中，数组下标通常从1开始更符合问题描述，但Python列表默认从0开始索引。这种差异需要特别注意，也是许多bug的来源。

2. 三种Python解法深度解析

2.1 基础递推法：显式处理边界条件

这是最直观的解法，直接按照问题描述实现状态转移方程。我们显式地处理三种情况：

1. 起点位置(1,1)
2. 第一行或第一列
3. 其他普通位置

def basic_dp(m, n):
    # 创建(m+1)×(n+1)的二维数组，初始化为0
    dp = [[0]*(n+1) for _ in range(m+1)]
    dp[1][1] = 1  # 初始条件
    
    for i in range(1, m+1):
        for j in range(1, n+1):
            if i == 1 and j == 1:
                continue  # 已初始化
            if i == 1:  # 第一行
                dp[i][j] = dp[i][j-1]
            elif j == 1:  # 第一列
                dp[i][j] = dp[i-1][j]
            else:  # 一般情况
                dp[i][j] = dp[i-1][j] + dp[i][j-1]
    
    return dp[m][n]

性能特点 ：

• 时间复杂度：O(m×n) —— 必须填充整个二维数组
• 空间复杂度：O(m×n) —— 需要存储整个dp表
• 优点：逻辑清晰，易于理解和调试
• 缺点：空间占用较大，对于极大棋盘可能内存不足

2.2 优化递推法：利用0下标简化逻辑

聪明的选手会发现，我们可以利用数组的0下标位置来统一处理边界条件，使代码更简洁。这种方法的关键在于：

• 将dp数组初始化为全0
• 保持dp[1][1] = 1
• 让递推公式自动处理边界情况

def optimized_dp(m, n):
    dp = [[0]*(n+1) for _ in range(m+1)]
    dp[1][1] = 1
    
    for i in range(1, m+1):
        for j in range(1, n+1):
            if i == 1 and j == 1:
                continue
            dp[i][j] = dp[i-1][j] + dp[i][j-1]
    
    return dp[m][n]

为什么这样可行？

• 当i=1时，dp[0][j] = 0，所以dp[1][j] = dp[0][j] + dp[1][j-1] = dp[1][j-1]
• 当j=1时，dp[i][0] = 0，所以dp[i][1] = dp[i-1][1] + dp[i][0] = dp[i-1][1]
• 这样边界情况就被自动处理了，无需特殊判断

2.3 记忆化递归：自顶向下的思考方式

对于习惯递归思维的选手，可以采用记忆化搜索（Memoization）的方法。这种方法更符合人类自然思考过程：

1. 从终点开始思考
2. 递归地分解问题
3. 存储已计算的结果避免重复计算

def memoization(m, n):
    memo = [[-1]*(n+1) for _ in range(m+1)]
    
    def helper(i, j):
        if i == 1 or j == 1:
            return 1
        if memo[i][j] != -1:
            return memo[i][j]
        memo[i][j] = helper(i-1, j) + helper(i, j-1)
        return memo[i][j]
    
    return helper(m, n)

记忆化递归的特点 ：

• 时间复杂度：O(m×n)（每个子问题只计算一次）
• 空间复杂度：O(m×n)（需要存储记忆表+递归栈）
• 优点：代码更接近数学定义，易于验证正确性
• 缺点：递归深度过大时可能栈溢出（Python默认递归深度约1000）

3. 边界条件与常见错误分析

在竞赛中，"移动路线"看似简单，但边界条件的处理往往是失分的重灾区。以下是选手常犯的错误及解决方案：

3.1 下标越界问题

错误示例 ：

dp = [[0]*n for _ in range(m)]  # 错误！应该是(n+1)和(m+1)

正确做法 ： 由于题目描述通常从(1,1)开始，我们需要创建(m+1)×(n+1)的数组，忽略0下标或将其作为辅助空间。

3.2 初始化错误

常见错误 ：

• 忘记初始化dp[1][1] = 1
• 错误地将整个第一行和第一列初始化为1（只有在特定问题要求时才这样做）

3.3 空间优化技巧

对于极大棋盘，我们可以使用 滚动数组 优化空间：

def space_optimized(m, n):
    prev = [1] * (n+1)  # 上一行
    
    for i in range(2, m+1):
        curr = [0] * (n+1)
        curr[1] = 1  # 第一列
        for j in range(2, n+1):
            curr[j] = prev[j] + curr[j-1]
        prev = curr
    
    return prev[n]

这种优化将空间复杂度从O(m×n)降到了O(n)，特别适合处理行数极大的情况。

4. OpenJudge真题实战解析

让我们以OpenJudge NOI 2.6 2718题为例，展示完整的解题流程：

题目描述 ： 给定一个m×n的方格，从左上角(1,1)出发，每次只能向右或向下移动一格，求到右下角(m,n)的路径总数。

输入样例 ：

3 2

输出样例 ：

3

完整Python解答 ：

def main():
    m, n = map(int, input().split())
    
    # 方法1：基础递推
    dp = [[0]*(n+1) for _ in range(m+1)]
    dp[1][1] = 1
    
    for i in range(1, m+1):
        for j in range(1, n+1):
            if i == 1 and j == 1:
                continue
            if i == 1:
                dp[i][j] = dp[i][j-1]
            elif j == 1:
                dp[i][j] = dp[i-1][j]
            else:
                dp[i][j] = dp[i-1][j] + dp[i][j-1]
    
    print(dp[m][n])

if __name__ == "__main__":
    main()

关键测试用例 ：

输入 (m,n)	预期输出	检查重点
1 1	1	最小棋盘
1 5	1	单行情况
5 1	1	单列情况
2 2	2	简单非平凡情况
3 3	6	验证组合数正确性

竞赛技巧：在编写完代码后，务必用这些边界用例测试你的程序，确保没有遗漏任何特殊情况。