c++ - 递归函数程序——寻找使二维数组中的值之和最大化的路径

Question

我试图在二维数组中找到路径，以获得最大值，即路径中每个值的总和。

例如，这是我的两个数组，如下所示。

6 0 0
1 2 0
6 7 4

从 (0,0) 开始，找到具有最大总和值的路径。(路径只能指向以下两种方式，如果当前点是(y，x)，则下一条路径可以是(y+1，x)或(y+1，x+1))。

应用上述程序后，转换后的维度数组如下:

6 0 0      15 0 0   
8 9 0  ->  8 9 0  
6 7 4      6 7 4  

因此，解决方案是 15。我尝试使用递归函数编写如下代码。

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
#include <stdio.h>
#include <map>

using namespace std;

namespace DIAMONDPATH {
    int dia[2 * 100][100];
    int copy_dia[2 * 100][100];

    int path(int y, int x,int height) {
        if (height == y + 1) {
            return dia[y][x];
        }

        copy_dia[y][x] = max(dia[y][x]+path(y + 1, x,height), dia[y][x]+path(y + 1, x + 1,height));

        cout << "y : "<<y<<" x : "<<x<<" value : "<< copy_dia[y][x] << endl;
    }
    int do_main(int argc, const char *argv[]) {
        freopen("input.txt", "r", stdin);

        int TC;
        cin >> TC;

        while (TC--) {
            int N;
            cin >> N;

            memset(copy_dia, -1, sizeof(copy_dia));
            for (int i = 0; i < N; ++i) {
                for (int j = 0; j <= i; ++j) {
                    cin >> dia[i][j];
                }
            }


            for (int i = 0; i < N; ++i) {
                for (int j = 0; j < N ; ++j) {
                    cout << dia[i][j] << " ";
                }
                cout << endl;
            }




            int ret = path(0, 0,N);



            cout << endl;

        }
        return 0;
    }
}

#ifndef DRIVER

int main(int argc, const char *argv[]) {
    return DIAMONDPATH::do_main(argc, argv);
}

#endif

但是，我运行了我的代码，最终结果((0,0)的位置)不是我想要的值。它返回未知值。我不知道它是从哪里来的。

如您所见，路径函数是在我的数组中获取最优路径的最大值。然后我输入了如下的 3x3 维数组。

6 0 0
1 2 0
6 7 4

我尝试使用 printf 进行调试但我失败了，因为它是递归的并且很难理解和查看每个过程。因此，我在这里发布了我的问题，想知道如何调试它以及未知值从何而来？

谢谢。

Answer 1

当 height != y+1 时，您的 path() 不返回值(即:返回未定义的值)；建议:添加一条 return 指令，例如

int path(int y, int x,int height) {
    if (height == y + 1) {
        return dia[y][x];
    }

    copy_dia[y][x] = max(dia[y][x]+path(y + 1, x,height), dia[y][x]+path(y + 1, x + 1,height));

    cout << "y : "<<y<<" x : "<<x<<" value : "<< copy_dia[y][x] << endl;

    return copy_dia[y][x];  //  <-----  add return
}