明白了，你想要一份C++ 信息学奥赛（OI）风格的递推 / 动态规划实战解析，涵盖 数塔问题和过河卒模型，附带 图例、状态转移方程，并且结合 C++ 实现示例。我给你整理一份完整、结构化的讲解。

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

1. 问题描述

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

示例数塔：

    2
   3 4
  6 5 7
 4 1 8 3

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

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)
只能向下或向右下移动
每个位置路径数 = 上方 + 左上方

示例棋盘：

1
1 1
1 2 1
1 3 3 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]类杨辉三角 / 组合数
  • 关键技巧
    1. DP 数组初始化正确
    2. 边界条件处理（左边界 / 右边界）
    3. 自底向上递推，减少重复计算
    4. 可进一步优化为 一维数组（滚动数组）节省空间