C++信息学奥赛递推-动态规划数塔与过河卒模型实战解析图例+详解+状态转移方程

wangjinjin180

323人浏览 · 2025-11-04 15:22:30

wangjinjin180 · 2025-11-04 15:22:30 发布

一、数塔问题（Triangle / Number Pyramid）

1. 问题描述

给定一个数塔（高度为 (n)），每个位置有一个数字。从顶部开始，每步可以向左下或右下走，求从顶到底的路径最大和（或最小和）。

示例数塔：

目标：求从顶到底的最大路径和。

2. 状态定义

设 f[i][j] 表示 走到第 i 层第 j 个数字的最大路径和（1-based）。
层数从 1 到 n，j 表示每层的第 j 个位置。

3. 状态转移方程

[
f[i][j] = \text{max}(f[i-1][j-1], f[i-1][j]) + a[i][j]
]

a[i][j]：塔中第 i 层第 j 个数字
边界条件：
- f[1][1] = a[1][1]
- 对于每层边界：
  - 左边界 f[i][1] = f[i-1][1] + a[i][1]
  - 右边界 f[i][i] = f[i-1][i-1] + a[i][i]

4. 图示说明

f[i][j] = max(f[i-1][j-1], f[i-1][j]) + a[i][j]

    2
   3 4
  6 5 7
 4 1 8 3

f[3][2] = max(f[2][1], f[2][2]) + 5 = max(5,7) + 5 = 12

5. C++ 实现

#include <bits/stdc++.h>
using namespace std;

const int N = 110;
int n;
int a[N][N];
int f[N][N];

int main() {
    cin >> n;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=i;j++)
            cin >> a[i][j];

    f[1][1] = a[1][1];
    for(int i=2;i<=n;i++) {
        for(int j=1;j<=i;j++) {
            if(j == 1)
                f[i][j] = f[i-1][j] + a[i][j];
            else if(j == i)
                f[i][j] = f[i-1][j-1] + a[i][j];
            else
                f[i][j] = max(f[i-1][j-1], f[i-1][j]) + a[i][j];
        }
    }

    int ans = 0;
    for(int j=1;j<=n;j++)
        ans = max(ans, f[n][j]);
    cout << ans << endl;
    return 0;
}

二、过河卒模型（River Crossing Pawn）

1. 问题描述

在一个 (n \times n) 棋盘上，一个卒（pawn）只能向下走或者斜向右下走。求从左上角到右下角的不同路径数。

类似于数塔，但棋盘规则不同
可以用 DP 统计路径数

2. 状态定义

f[i][j]：卒走到 (i,j) 的路径数

3. 状态转移方程

[
f[i][j] = f[i-1][j] + f[i-1][j-1]
]

边界条件：
- f[1][1] = 1
- f[i][0] = 0（左边界外不存在）

4. 图示说明

卒初始位置 (1,1)
只能向下或向右下移动
每个位置路径数 = 上方 + 左上方

示例棋盘：

类似杨辉三角

5. C++ 实现

#include <bits/stdc++.h>
using namespace std;

const int N = 110;
int f[N][N];
int n;

int main() {
    cin >> n;

    f[1][1] = 1; // 起点
    for(int i=2;i<=n;i++)
        for(int j=1;j<=i;j++)
            f[i][j] = f[i-1][j-1] + f[i-1][j];

    for(int i=1;i<=n;i++){
        for(int j=1;j<=i;j++)
            cout << f[i][j] << " ";
        cout << endl;
    }

    cout << "路径总数：" << f[n][n] << endl;
    return 0;
}

三、总结

问题	状态	转移方程	特点
数塔	`f[i][j]` 最大路径和	`f[i][j] = max(f[i-1][j-1], f[i-1][j]) + a[i][j]`	DP 经典自底向上
过河卒	`f[i][j]` 路径数	`f[i][j] = f[i-1][j] + f[i-1][j-1]`	类杨辉三角 / 组合数