2

问题如下

考虑下面显示的数字三角形。编写一个程序，计算可以在从顶部开始到底部某处结束的路线上传递的最大数字总和。每一步都可以对角线向左或向右对角线向下。

        7

      3   8

    8   1   0

  2   7   4   4

4   5   2   6   5

在上面的示例中，路由7 -> 3 -> 8 -> 7 -> 5产生的总和最高：30。

我有以下错误

 Execution error: Your program (`numtri') used more than the
    allotted runtime of 1 seconds (it ended or was stopped at 1.674
    seconds) when presented with test case 6. It used 6080 KB of
    memory.

我的程序适用于输入 <=8 三角形大小。但是，当三角形大小超过 8 时，它会失败。我不知道为什么会这样。请帮忙。

这是我的代码：

#define MAX 1000

int max=0,a[MAX][MAX];

void dfs(int i,int j,int end,int sum)
{
 if(i<=end)
 {   
      sum += a[i][j];
      dfs(i+1,j,end,sum);
      dfs(i+1,j+1,end,sum);
 }
 else 
 {
      if(sum>max)  
      max = sum;

 }
}

int main () {

FILE *fin  = fopen ("numtri.in", "r");
FILE *fout = fopen ("numtri.out", "w");
int r,i,j;

fscanf(fin,"%d",&r);

for(i = 1;i<=r;i++)
 for(j = 1;j<=i;j++)
  fscanf(fin,"%d",&a[i][j]);

dfs(1,1,r,0);

fprintf(fout,"%d\n",max);

fclose(fin);
fclose(fout);
return 0;
}

它适用于前 5 个测试用例，但在具有 199 个三角形大小的第 6 个测试用例中失败。

4

4 回答 4

2

每次您的程序遇到金字塔中的特定点时，它都会计算到底部的最佳路径。但是，您可以观察到每个点多次遇到，因此多次计算最佳路径。因此，您的程序在指数时间内运行。

如果您改为保存三角形中某个点（在此处dp[i][j]）可实现的最大和，并在再次达到该点后重用该值而不是重新计算它，您的程序将快得多。那是因为这个算法只访问金字塔中的每个点一次。这称为自顶向下动态规划。

#include<string.h>
#include<stdio.h>
#define MAX_N 1005

int a[MAX_N][MAX_N];
int dp[MAX_N][MAX_N];

int max(int a, int b)
{
  return a > b ? a : b;
}

int dfs(int i,int j,int end)
{
  if(dp[i][j] != -1)
  {
    return dp[i][j];
  }
  else if(i <= end)
  {
    return dp[i][j] = a[i][j] + max(dfs(i+1,j,end), dfs(i+1,j+1,end));
  }
  else
  {
    return 0;
  }
}

int main () {
  FILE *fin  = fopen ("numtri.in", "r");
  FILE *fout = fopen ("numtri.out", "w");
  int r,i,j;

  memset(dp, -1, sizeof dp);

  fscanf(fin,"%d",&r);

  for(i = 1;i<=r;i++)
    for(j = 1;j<=i;j++)
      fscanf(fin,"%d",&a[i][j]);

  fprintf(fout,"%d\n", dfs(1,1,r));

  fclose(fin);
  fclose(fout);
  return 0;
}
于 2013-05-25T14:44:34.437 回答
1

由于以下原因，使用 DFS 解决此问题效率低下：考虑一条先右后左的路径，另一条先左后右的路径。这些路径现在位于同一个点，从该点开始的路径将被计算两次。在金字塔的较低层，情况更糟，运行时间呈指数增长。

您需要做的就是所谓的动态规划。我们利用这个问题表现出最优子结构（对于一个最大的路径，所有子路径必须是最大的）和重叠子问题（上述行为）这一事实。这使我们可以避免做不必要的工作。

对此有两种可能的方法。

  1. 自上而下的记忆：做你的dfs，但是当你返回时保存给定单元格的计算值。这样，当您再次访问一个单元格时，您不必从该单元格执行 dfs，并且可以立即返回。

  2. 自下而上：从底行开始，并保留从当前行中的每个单元格开始可实现的最大总和的列表。首先，这只是底部的数字。然后，对于接下来的行，第 i 行的单元格 j 将具有最大总和：a[i][j] + max(maxsum[i+1][j], maxsum[i+1][j+1])

有关更多信息，请阅读 wikipedia 或您最喜欢的算法书籍中的动态编程。

于 2013-05-25T14:45:06.707 回答
0

dfs()例程中的递归提供dfs了搜索深度呈指数增长的运行时，它所做的大部分工作都是多余的。对于这个问题，有一个简单的非递归解决方案。不是递归到，而是维护当前级路径最大值dfs的向量。v要更深一层，请复制v到工作向量w；然后将每个元素设置 v[j]为a[i][j]和 中的较大w[j]者w[j+1]。

于 2013-05-25T14:43:19.007 回答
0

除了使用 dp 之外，它可以使用 BFS 来完成，因为当您遇到访问过的节点时，您可以简单地更改其值，因为您直到图结束才遍历，但您必须非常小心内存。这是我在 USACO Grader 中有效的代码：

#include <bits/stdc++.h>
    using namespace std;
    
    typedef long long ll;
    typedef long double ld;
    typedef vector<long long> vi;
    typedef pair<long long,long long> pi;
    typedef vector<pi> vpi;
    
    #define FOR(i, a, b) for(ll i=ll(a); i<ll(b); i++)
    #define ROF(i, a, b) for(ll i=ll(a); i>=ll(b); i--)
    #define f first
    #define s second
    #define pb emplace_back
    #define mp make_pair
    #define SQ(a) (a)*(a)
    #define all(a) (a).begin(), (a).end()
    
    
    int main() {
    ifstream cin("numtri.in");
    ofstream cout("numtri.out");
    int n;
    
    int adjacency_list[500500];
    int matrix[1005][1005];
    
    bool visited[500500];
    int value[500500];
    
    int total[500500];
    int maxnum=0;
    
    cin>>n;
    int s=0,x=0;
    for(int i=0;i<n;i++){
    s++;
    for(int j=0;j<s;j++){
      cin>>value[x];
      total[x]=0;
      matrix[i][j]=x;
    x++;
    }
    }
    s=0;
    
    
    for(int i=0;i<n-1;i++){
    s++;
    for(int j=0;j<s;j++){
      adjacency_list[matrix[i][j]]=(matrix[i+1][j]);
    
    }
    }
 
    
     
    total[0]=value[0];
    queue<int>q;
    q.push(0);
    while(!q.empty()){
      int current=q.front();
      q.pop();
    
    if(current<((n*(n+1) )/2)-1-(n-1 )  ){
    
    int i =adjacency_list[current];
      if(!visited[i]){
        q.push(i);
        total[i]=total[current]+value[i];
        //cout<<total[i];
      }
      else{
    if(total[current]+value[i]>total[i]){
      total[i]=total[current]+value[i];
    }
      }
      maxnum=max(total[i],maxnum);
      visited[i]=1;
    
    i =adjacency_list[current]+1;
      if(!visited[i]){
        q.push(i);
        total[i]=total[current]+value[i];
       
      }
      else{
    if(total[current]+value[i]>total[i]){
      total[i]=total[current]+value[i];
    }
      }
      maxnum=max(total[i],maxnum);
      visited[i]=1;
    }
    }
    
    cout<<maxnum<<endl;
        return 0;
    }
于 2020-07-03T22:41:51.910 回答