当前位置：首页 > article >正文

于动态规划的启幕之章，借 C++ 笔触绘就算法新篇

article 2025/2/3 7:17:49

注意：代码由易到难

P1216 [IOI 1994] 数字三角形 Number Triangles

题目链接：[IOI 1994] 数字三角形 Number Triangles - 洛谷

题目描述

观察下面的数字金字塔。

写一个程序来查找从最高点到底部任意处结束的路径，使路径经过数字的和最大。每一步可以走到左下方的点也可以到达右下方的点。

在上面的样例中，从 7→3→8→7→57→3→8→7→5 的路径产生了最大权值。

输入格式

第一个行一个正整数 �r ,表示行的数目。

后面每行为这个数字金字塔特定行包含的整数。

输出格式

单独的一行,包含那个可能得到的最大的和。

输入输出样例

输入 #1
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5 
输出 #1
30
说明/提示

【数据范围】
对于 100%100% 的数据，1≤r≤1000，所有输入在 [0,100] 范围内。

思路：动态规划，由局部最优达到全局最优

本题属于动态规划中最优子问题类

代码一（dfs+记忆化数组）注意：本代码有一个测试点超时

#include<iostream>  // 包含标准输入输出流库
#include<algorithm> // 包含算法库，用于使用 max 函数
using namespace std;

int r; // 全局变量，表示三角形的行数
int arr[1001][1001]; // 用于存储数字三角形的数组，大小为 1001x1001
int memory[1001][1001] = {0}; // 用于记忆化搜索的数组，初始化为 0

// 深度优先搜索（DFS）函数，用于计算从 (x, y) 到三角形底部的最大路径和
int dfs(int x, int y) {
    if (memory[x][y] != 0) return memory[x][y]; // 如果已经计算过 (x, y) 的结果，直接返回
    int mid;
    if (x > r || y > x) { // 如果超出三角形范围
        mid = 0; // 返回 0
    } else {
        // 递归计算从 (x, y) 向下和向右下两个方向的最大路径和，并加上当前节点的值
        mid = max(dfs(x + 1, y), dfs(x + 1, y + 1)) + arr[x][y];
    }
    memory[x][y] = mid; // 将结果存储到记忆化数组中
    return mid; // 返回当前节点的最大路径和
}

// 主逻辑函数，读取输入并调用 DFS
void solution() {
    cin >> r; // 输入三角形的行数
    for (int i = 1; i <= r; i++) { // 逐行读取三角形的每一行
        for (int j = 1; j <= i; j++) { // 逐个读取当前行的每个数字
            cin >> arr[i][j]; // 存储到 arr 数组中
        }
    }
    int maxSum = dfs(1, 1); // 从三角形顶部 (1, 1) 开始计算最大路径和
    cout << maxSum << endl; // 输出最大路径和
}

int main() {
    ios::sync_with_stdio(false); // 关闭同步，提高输入输出效率
    cin.tie(nullptr); // 解绑 cin 和 cout，进一步提高效率
    int T = 1; // 测试用例数量，默认为 1
    // cin >> T; // 如果需要多个测试用例，可以取消注释
    while (T--) { // 对每个测试用例调用 solution 函数
        solution();
    }
    return 0; // 程序结束
}

代码二（动态规划，通过）

#include<iostream>
#include<algorithm>
using namespace std;

int r; // 三角形的行数
int arr[1002][1002]; // 存储输入的数字三角形
int mid[1002][1002] = {0}; // 动态规划数组，用于存储从底部到当前点的最大路径和

// 解决数字三角形问题的函数
void solution()
{
    cin >> r; // 输入三角形的行数
    for (int i = 1; i <= r; i++) // 逐行读取三角形的数据
    {
        for (int j = 1; j <= i; j++) // 每行的列数等于行号
        {
            cin >> arr[i][j]; // 输入当前元素
        }
    }

    // 动态规划从三角形的底部向上计算最大路径和
    for (int i = r; i >= 1; i--) // 从最后一行开始向上遍历
    {
        for (int j = 1; j <= i; j++) // 遍历当前行的每个元素
        {
            // 当前点的最大路径和等于当前点的值加上其下方两个点中较大的值
            mid[i][j] = max(mid[i + 1][j], mid[i + 1][j + 1]) + arr[i][j];
        }
    }
    cout << mid[1][1] << endl; // 输出从顶部到底部的最大路径和
}

int main()
{
    ios::sync_with_stdio(false); // 关闭同步，提高输入输出效率
    cin.tie(nullptr); // 解绑cin和cout，进一步提高效率
    int T = 1; // 测试用例数量（这里固定为1）
    // cin >> T; // 如果需要处理多组数据，可以取消注释
    while (T--) // 处理每一组数据
    {
        solution(); // 调用solution函数解决问题
    } 
    return 0; // 程序结束
}

代码三（动态规划+滚动数组）

#include<iostream>
#include<algorithm>
#include<cmath>
#include<iomanip>
using namespace std;
#define av(y) setprecision(y)<<fixed;

int r; // 三角形的行数
int arr[1002][1002]; // 存储输入的数字三角形
int mid[1002] = {0}; // 动态规划数组，用于存储从底部到当前点的最大路径和（一维数组）

// 解决数字三角形问题的函数
void solution()
{
    cin >> r; // 输入三角形的行数
    for (int i = 1; i <= r; i++) // 逐行读取三角形的数据
    {
        for (int j = 1; j <= i; j++) // 每行的列数等于行号
        {
            cin >> arr[i][j]; // 输入当前元素
        }
    }

    // 动态规划从三角形的底部向上计算最大路径和
    for (int i = r; i >= 1; i--) // 从最后一行开始向上遍历
    {
        for (int j = 1; j <= i; j++) // 遍历当前行的每个元素
        {
            // 当前点的最大路径和等于当前点的值加上其下方两个点中较大的值
            // 这里使用一维数组 mid 来存储中间结果
            mid[j] = max(mid[j], mid[j + 1]) + arr[i][j];
        }
    }
    cout << mid[1] << endl; // 输出从顶部到底部的最大路径和
}

int main()
{
    ios::sync_with_stdio(false); // 关闭同步，提高输入输出效率
    cin.tie(nullptr); // 解绑cin和cout，进一步提高效率
    int T = 1; // 测试用例数量（这里固定为1）
    // cin >> T; // 如果需要处理多组数据，可以取消注释
    while (T--) // 处理每一组数据
    {
        solution(); // 调用solution函数解决问题
    } 
    return 0; // 程序结束
}

查看全文

http://www.kler.cn/a/529443.html