求5×5网格中仅向右/向下移动的最大得分路径实现方案

嘿，我来帮你搞定这个核心逻辑！你的问题是典型的**动态规划（Dynamic Programming）**应用场景，刚好适配只能向右/向下移动的限制条件。下面我会一步步解释思路，然后帮你修改代码实现功能。

核心思路：动态规划表（DP Table） #

我们可以创建一个和原网格大小相同的DP表dp[i][j]，用来存储从起点(0,0)走到(i,j)时能获得的最大得分。状态转移规则很清晰：

• 起点(0,0)的最大得分就是它本身的分值：dp[0][0] = field[0][0]
• 第一行的格子只能从左边（同一行的前一个格子）过来，所以dp[0][j] = dp[0][j-1] + field[0][j]
• 第一列的格子只能从上面（同一列的前一个格子）过来，所以dp[i][0] = dp[i-1][0] + field[i][0]
• 其他位置的格子可以从上方或左方过来，取两者中的最大得分加上当前格子的分值：dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + field[i][j]

最后，右下角dp[4][4]（因为你的网格是5x5，索引从0到4）的值就是我们要找的最大得分。如果需要，我们还可以回溯DP表找出具体的路径。

修改后的完整代码 #

我已经把核心逻辑集成到你的现有代码里了，保留了你的输入和可视化部分：

#include <iostream>
#include <algorithm> // 用于max函数，也可以自己实现判断逻辑
using namespace std;

int main() {
    int f = 0; // 带分值的格子数量
    const int fSpaces = 5; // 网格大小固定为5x5
    int field[fSpaces][fSpaces]; // 游戏网格
    int x = 0, y = 0; // 坐标
    int n = 0; // 对应分值
    int dp[fSpaces][fSpaces]; // 动态规划表，存储到每个格子的最大得分

    // 初始化网格所有值为0
    for(int i = 0; i < fSpaces; i++){
        for(int j = 0; j < fSpaces; j++){
            field[i][j] = 0;
        }
    }

    // 输入模块
    cout << "How many fields?: ";
    cin >> f;
    cout << "Coordinates (x y score):" << endl;
    for(int i = 0; i < f; i++){
        cin >> x >> y >> n;
        field[x][y] = n;
    }

    // 可视化网格
    cout << "\nGame Grid:" << endl;
    for(int i = 0; i < fSpaces; i++){
        for(int j = 0; j < fSpaces; j++){
            cout << field[j][i] << " _|_ ";
        }
        cout << endl;
    }

    // ------------------------------
    // 核心：动态规划计算最大得分
    // ------------------------------
    // 初始化起点
    dp[0][0] = field[0][0];

    // 填充第一行（只能从左边来）
    for(int j = 1; j < fSpaces; j++){
        dp[0][j] = dp[0][j-1] + field[0][j];
    }

    // 填充第一列（只能从上面来）
    for(int i = 1; i < fSpaces; i++){
        dp[i][0] = dp[i-1][0] + field[i][0];
    }

    // 填充其他位置（取上方/左方的最大得分）
    for(int i = 1; i < fSpaces; i++){
        for(int j = 1; j < fSpaces; j++){
            dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + field[i][j];
        }
    }

    // 输出最大得分
    cout << "\nMax Score Path Total: " << dp[fSpaces-1][fSpaces-1] << endl;

    // （可选）回溯输出具体路径
    cout << "\nPath from (0,0) to (" << fSpaces-1 << "," << fSpaces-1 << "):" << endl;
    int i = fSpaces-1, j = fSpaces-1;
    cout << "(" << i << "," << j << ")";
    while(i != 0 || j != 0){
        if(i == 0){ // 只能从左边来
            j--;
        } else if(j == 0){ // 只能从上面来
            i--;
        } else {
            // 看哪个方向的得分更大，就从哪个方向回溯
            if(dp[i-1][j] > dp[i][j-1]){
                i--;
            } else {
                j--;
            }
        }
        cout << " <- (" << i << "," << j << ")";
    }
    cout << endl;

    return 0;
}

测试你的输入示例 #

用你提供的输入测试：

3
0 1 5
2 2 10
2 0 1

运行后会输出：

• 正确的网格可视化效果
• 最大得分：15（最优路径为(0,0) → (0,1) → (0,2) → (1,2) → (2,2) → (3,2) → (4,2) → (4,3) → (4,4)，得分总和为5+10=15）
• 倒序的路径回溯结果

注意事项 #

• 我把fSpaces改成了const，因为网格大小固定，代码更规范。
• 如果不想引入<algorithm>头文件，可以把max函数替换成三元表达式：dp[i][j] = (dp[i-1][j] > dp[i][j-1] ? dp[i-1][j] : dp[i][j-1]) + field[i][j]。
• 路径回溯是倒序输出的，如果你需要正序，可以把路径存在数组里再反向输出。

内容的提问来源于stack exchange，提问作者Cnylloo