动态规划解决网格路径问题：蓝桥杯真题解析

1. 题目解析与算法思路

这道题目来自蓝桥杯2020年第十一届省赛真题，考察的是动态规划算法的应用。题目要求在一个n×m的方格中，从左上角(1,1)走到右下角(n,m)，每次只能向右或向下移动，且不能经过行号和列号都为偶数的格子。我们需要计算所有可能的路径数。

1.1 问题建模

首先我们需要将这个问题转化为数学模型。可以将方格看作一个二维矩阵，其中每个格子(i,j)表示从起点到该格子的路径数。题目给出的限制条件是：

1. 不能经过行号和列号都为偶数的格子（即i%2==0 && j%2==0的格子）
2. 每次移动只能向右或向下

1.2 动态规划状态定义

我们定义一个二维数组f[i][j]，表示从起点(1,1)到格子(i,j)的路径数。根据题目要求，我们需要考虑以下几种情况：

1. 边界条件：第一行和第一列的格子，由于只能从一个方向过来（第一行只能从左边过来，第一列只能从上面过来），所以路径数都是1
2. 特殊限制：当i和j都为偶数时，f[i][j]=0，因为不能经过这样的格子
3. 一般情况：f[i][j] = f[i-1][j] + f[i][j-1]，即从上方或左方过来的路径数之和

2. 代码实现详解

2.1 基础框架

cpp复制#include<iostream>
using namespace std;
int f[30][30];  // 定义足够大的二维数组存储路径数

int main(){
    int n,m;
    cin>>n>>m;  // 输入方格的行列数
    // 初始化边界条件
    for(int i=1;i<=n;i++){
        f[i][1]=1;  // 第一列的初始化
    }
    for(int j=1;j<=m;j++){
        f[1][j]=1;  // 第一行的初始化
    }
    // 动态规划填充过程
    for(int i=2;i<=n;i++){
        for(int j=2;j<=m;j++){
            if(i%2==0 && j%2==0){
                f[i][j]=0;  // 行和列都为偶数的格子不能经过
            }else{