数字三角形

答案为：30

递归，需要用到二维数组，用D(i, j)表示第r行第j个数字，函数MaxSum(r, j):表示从D(i, j)到底部的各条路径中。最佳路径的数字之和，则问题转换为求MaxSum(1, 1)。或者用二维数组进行存储优化，改用一维数组解决

递归：

#include 
#include 

using namespace std;

#define MAX 101

int n;
int d[MAX][MAX];

int MAxSum(int i, int j) {
  if(i==n) return d[i][j];

  int x = MAxSum(i+1, j);
  int y = MAxSum(i+1, j+1);

  return max(x, y)+d[i][j];
}

int main()
{
  cin>>n;
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= i; ++j) {
      cin>>d[i][j];
    }
  }
  cout< 用一维数组解决， 如下excel表格截图，从下到上。从左往右进行一行一行计算
#include 
#include 

using namespace std;

#define MAX 101

int n;
int d[MAX][MAX];
int* maxsum;

int main()
{
  cin>>n;
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= i; ++j) {
      cin>>d[i][j];
    }
  }
  maxsum = d[n]; //maxsum指向第n行
  for (int i = n-1; i >= 1; --i) {
  	for (int j = 1; j <= i; ++j) {
  		maxsum[j] = max(maxsum[j], maxsum[j+1]) + d[i][j];
	  }
  }
  cout< 
 
 
 
					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/5714652.html