c++ - 将 C++ 函数转换为递归函数

Question

我正在查看一个函数，需要将其转换为动态规划形式。但是我很难理解这个函数中使用的逻辑(基本情况是什么？)，这个函数的原作者不再可以提问，我无法对他的工作做出正面或反面的判断，并且有0 个文档可用。

描述:

这个函数接受一个正整数矩阵，并找到最大和 从矩阵的每一列中选择一个元素，从左到右移动。当你穿过 矩阵逐列，根据您的方式，您的总和会受到惩罚 相对于您之前的两个位置移动。如果您选择的下一行介于前两行之间 选择行，没有惩罚；但是，上面每一行的总和都会受到 2 的惩罚 前两项的最大值或低于前两项的最小值。

int calSum(int row, int cols, vector<vector<int>> inputArray, vector<int> *outputArray){

    int ans[row][cols][row];
    int index[row][cols][row];

    int firstCol[row];

    for(int i=0;i<row;i++){

        firstCol[i]= inputArray[i][0] - 2*(i);
    }

    for(int i=0;i<row;i++){

        for(int j=0;j<row;j++){
            int penalty;

            if(i<=j){
                penalty=0;
            }else{
                penalty= 2* (i-j);
            }

            ans[i][1][j]= inputArray[i][1] - penalty+ firstCol[j];

        }
    }

    for(int j=2;j<cols;j++){

        for(int i=0;i<row;i++){


            int nextRow= i;

            for(int k=0;k<row;k++){

                int currRow= k;
                int ind=-1;
                int maxVal= INT_MIN;
                for(int l=0;l<row;l++){

                    int prevRow=l;
                    int max1= max(prevRow, currRow);
                    int min1= min(prevRow, currRow);

                    int penalty;
                    if(nextRow<=max1&&nextRow>= min1){
                        penalty=0;
                    }else if(nextRow>max1){
                        penalty= 2*(nextRow-max1);
                    }else{
                        penalty= 2*(min1-nextRow);
                    }

                    int val= -penalty+ inputArray[i][j] + ans[k][j-1][l];
                    if(val>maxVal){
                        maxVal=val;
                        ind=l;
                    }
                }

                ans[i][j][k]=maxVal;
                index[i][j][k]=ind;

            }

        }

    }

    int max=INT_MIN;
    int x=-1;
    int y=-1;

    for(int i=0;i<row;i++){

        for(int j=0;j<row;j++){

            if(ans[i][cols-1][j]>max){
                max= ans[i][cols-1][j];
                x=i;
                y=i;
            }

        }
    }

    for(int j=cols-1;j>=2;j--) {

        outputArray->push_back(x);
        int temp=x;
        x= y;
        y= index[temp][j][y];
    }

    outputArray->push_back(x);
    outputArray->push_back(y);

    return max;

}

我已尝试跟踪代码并不断迷失在逻辑中。非常感谢对此功能的基本解释。

Answer 1

核心数据结构 ans 的工作原理如下:ans[i][j][k] 是从 (k, 0) 到 (i, j)。 (注意这里使用 row,col 表示法来匹配程序中的表示法)

如果我们逐个循环遍历代码:

• 第一个 for 循环计算第一列中值的分数，考虑到行 > 1 的所有内容都会受到惩罚。
• 第二个 for 循环计算 ans[i][1][j]，或到第二列的最大路径，给定起始行 j 和结束行 i。

• 第三个 for 循环逐渐向右扩展 ans。对于每一列 j > 1，它通过找到一个最大化 (k, 0) 到 (l, j) 的 l 来填充 ans[i][j][k] -1) 到 (i, j)。第一部分可以看ans[k][j-1][l]，最后一步根据题中给出的规则计算。

  此循环还将 l 的最佳选择写入 ind 数据结构中，因此您可以稍后重建最佳路径。

• 第四个 for 循环简单地找到最大路径值并存储结束行。
• 最后的 for 循环通过回溯 ind 数据结构中的步骤来重建路径。