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

Question

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

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:

1. 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.

2. 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)

解.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 矩阵的链接列表的情况下使用递归简单地解决这个问题？动态规划是否适用于此问题。

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) 返回这个金字塔最重的路径。

          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) 返回正确的权重(分别为 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) 应该返回 244 = 9 + max(235, 55)。

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