如何使用递归来制定使用简单数组

Question

我是编码初学者。我想使用简单的递归和数组来解决以下问题。但我无法想象它。我使用 link list 想出了解决方案。以下是问题和我解决

的方法

Given n rows of integers, such that the ith row (1 <= i <= n) contains i integers. Using the following set of path rules, find the path having the maximum weight.

Path traversal rules:

A valid path sequence would be top-down i.e. begins with the integer in the first row, and traverses all rows selecting only one integer in each row.

From any jth integer in the ith row i.e. row[i][j], traversal can happen either downward (i.e. to row[i+1][j]) or diagonally downward to the right (i.e. to row[i+1][j+1]).

The weight of a Path is the sum of values of integers in the Path sequence.

Example:
    No. of Rows: 5 
        4 
        2    9 
        15   1    3 
        16   92  41  44 
        8   142  6    4    8 
Expected Output: 4, 2, 15, 92, 142 (Max weight is 255)

Sol.c

#include<stdio.h>
#include<stdlib.h>

int n,**ar;

struct n
{
 int i,j;
 int w;
 struct n *ptr;
};

struct n* maxweight(int i,int j,struct n* x)
{
 struct n* tmp=malloc(sizeof(struct n)),*t1,*t2;
 tmp->i=i;
 tmp->j=j;
 tmp->ptr=x;
 tmp->w=ar[i][j];
 if(x)tmp->w+=x->w;
 if(i==n-1)return tmp;
 t1=maxweight(i+1,j,tmp);
 t2=maxweight(i+1,j+1,tmp);
 if(t1->w>t2->w)return t1;
 return t2;
}

int main()
{
 int i,j;
 struct n * s;
 printf("Enter the value of n\n");
 scanf("%d",&n);
 ar=malloc(n*sizeof(int*));
 for(i=0;i<n;i++)
 {
  ar[i]=malloc((i+1)*sizeof(int));
  for(j=0;j<=i;j++)scanf("%d",&ar[i][j]);
 }
 s=maxweight(0,0,NULL);
 printf("MAX WEIGHT is :%d\nPATH: ",s->w);
 while(s)
 {
  printf("%d ",ar[s->i][s->j]);
  s=s->ptr;
 }
 printf("\n");
 return 0;
}

如何在不使用 n x n 矩阵的 link-list 的情况下使用递归简单地解决这个问题？动态规划适用于这个问题吗

Answer 1

重点计算前方路径的权重； 不要回头

首先解决一个微不足道的边缘案例。假设你到了最后一行。然后就没有什么可遵循的了；剩余路径的权重为零。

在代码中：

int getWeight(int i, int j)
{
    int remaining = 0;

在任何其他行中，您必须做出选择。你应该向左还是向右？由于此时无法知道哪一个是最好的，您只需要尝试两个方向：

    if (i < lastRow)
    {
        int weightLeft  = getWeight(i + 1, j);
        int weightRight = getWeight(i + 1, j + 1);

注意我递归调用了我自己的函数； 盲目相信该函数能够为剩余路径提出最佳权重！

两个方向都试过了，选择权重最高的一个：

        int best_j = weightLeft > weightRight ? j : j + 1;

现在我们再走一遍选择的路。

        remaining = getWeight(i + 1, best_j);
    }

这不是很有效，但它有助于收集最佳路径的各个步骤。我将使用一个简单的数组 pathColumns.

    pathColumns[i] = j;

最后，我们需要对值求和。

    return row[i][j] + remaining;
}

要让整个事情动起来，只需调用该函数，并将顶部单元格的坐标传递给它。出于实际原因，我将所有数组设为基数为 0。所以最上面的单元格是 row[0][0].

printf("Optimal weight: %d\n", getWeight(0, 0));

综合起来：

#include <stdio.h>

#define n 5

int pathColumns[n] = {0};

int row[n][n] =
{
    {4},
    {2, 9},
    {15, 1, 3},
    {16, 92, 41, 44},
    {8, 142, 6, 4, 8}
};

int getWeight(int i, int j)
{
    int remaining = 0;
    if (i < n-1)    /* with base-0, the last row is n-1 */
    {
        int weightLeft  = getWeight(i + 1, j);
        int weightRight = getWeight(i + 1, j + 1);
        int best_j = weightLeft > weightRight ? j : j + 1;
        remaining = getWeight(i + 1, best_j);
    }
    pathColumns[i] = j;
    return row[i][j] + remaining;
}

int main()
{
    int i;
    printf("Optimal weight: %d\n", getWeight(0, 0));
    for (i = 0; i < n; i++)
    {
        int j = pathColumns[i];
        printf("(%d, %d) = %d\n", i+1, j+1, row[i][j]);
        /* NOTE: +1 is a correction to bring the output back to base-1 */
    }
    return 0;
}

输出：

Optimal weight: 255
(1, 1) = 4
(2, 1) = 2
(3, 1) = 15
(4, 2) = 92
(5, 2) = 142

工作原理

我们想要 getWeight(0, 0) 到 return 这个金字塔最重的路径。

          4  <---- (0, 0) is our starting point
         / \
        2   9
      /  \ /  \
    15    1    3
    / \  / \  / \
  16   92   41   44
 /  \ /  \ /  \ /  \
8   142   6    4    8

递归算法进行两次递归调用。

getWeight(1, 0) 必须获得起点下方和左侧的子金字塔的最重路径。
getWeight(1, 1) 必须获得起点下方和右侧的子金字塔的最重路径。

两个子金字塔：

        2  <--- (1, 0)         9  <--- (1, 1)
      /  \                    /  \
    15    1                  1    3
    / \  / \                / \  / \
  16   92   41            92   41   44
 /  \ /  \ /  \          /  \ /  \ /  \
8   142   6    4      142    6    4    8

假设 getWeight(1, 0) 和 getWeight(1, 1) return 权重正确（分别为 251 和 244），剩下要做的就是选择最高的一个 (251) 并添加大金字塔的最高价值（4）。结果是 255.

我们所做的是减少一个问题（计算高度为 5 的金字塔的最大重量），这样我们就剩下两个较小的问题需要解决（计算高度为 4 的金字塔的最大重量）。同样的，我们可以将身高4的问题简化为身高3的问题。例如，getWeight(1, 1)将进行两次递归调用getWeight(2, 1)和getWeight(2, 2)：

       1  <--- (2, 1)      3  <--- (2, 2)
      / \                 / \
    92   41             41   44
   /  \ /  \           /  \ /  \
142    6    4         6    4    8

getWeight(1, 1) 应该 return 244 = 9 + max(235, 55).

继续这种方式，我们最终解决了高度为 1 的金字塔的问题。这些是原始金字塔底部的值（8、142、6、4 和 8）。递归到此结束；高度为 1 的金字塔只不过是一个节点。该节点的值是通过该金字塔的（唯一）路径的权重。

如何使用递归来制定使用简单数组

how to use recursion to formulate using simple array

c

recursion

dynamic-programming

backtracking

工作原理