动态规划——数字三角形

时间:2022-11-04 21:53:25

题目:  

7

3  8

8  1  0

2  7  4  4

4  5  2  6  5

在上面的数字三角形中寻找一条从顶部到底边的路径,使得路径上所经过的数字之和最大。路径上的每一步都只能往左下或右下走。只需要求出这个最大和即可,不必给出具体路径。(三角形的行数大于1小于等于100,数字为0-99)

 

解题思路:

用二维数组存放数字三角形。

D(r,j):第r行第j个数字(r,j从1开始算)

MaxSum(r,j):从D(r,j)到底边的各条路径中,最佳路径的数字之和。

问题:求MaxSum(1,1)

 

典型的递归问题。D(r,j)出发,下一步只能走D(r+1,j)或者D(r+1,j+1)。故对于N行的三角形:

if(r==N)

    MaxSum(r,j) = D(r,j)

else

    MaxSum(r,j) = Max { MaxSum(r+1,j) , MaxSum(r+1 , j+1) } + D(r,j)

 

 递归代码:

#include "stdafx.h"
#include
<iostream>
#include
<algorithm>

#define MAX 101
using namespace std;

int D[MAX][MAX];
int n;

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 _tmain(int argc, _TCHAR* argv[])
{
int i,j;
cin
>>n;

for(int i=1;i<=n;i++)
for(int j=1;j<=i;j++)
cin
>>D[i][j];
cout
<<MaxSum(1,1)<<endl;
return 0;
}

 

记忆型递归代码:

#include "stdafx.h"
#include
<iostream>
#include
<algorithm>

#define MAX 101
using namespace std;

int D[MAX][MAX];
int maxSum[MAX][MAX];
int n;

int MaxSum(int i,int j)
{
if(maxSum[i][j]!=-1)
return maxSum[i][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 _tmain(int argc, _TCHAR* argv[])
{
int i,j;
cin
>>n;

for(int i=1;i<=n;i++)
for(int j=1;j<=i;j++){
cin
>>D[i][j];
maxSum[i][j]
=-1;
}
cout
<<MaxSum(1,1)<<endl;
return 0;
}

 

将递归转化为递推:

比如

7

3  8

8  1  0

2  7  4  4

4  5  2  6  5

从最下面一层 4 5 2 6 5开始往上面推,比如:max(4,5)+2=7,用新得到的7存放到原来2的位置,这样反复循环往上计算,最终得到30。

因此规律就是:maxSum[i][j] = max(maxSum[i+1][j],maxSum[i+1][j+1]) + D[i][j]。

30

23  21

20  13  10

7    12  10   10

4    5    2     6     5

 

递推代码:

#include "stdafx.h"
#include
<iostream>
#include
<algorithm>

using namespace std;

#define MAX 101
int D[MAX][MAX];
int n;
int maxSum[MAX][MAX];

int _tmain(int argc, _TCHAR* argv[])
{
int i,j;
cin
>>n;

for(int i=1;i<=n;i++)
{
for(int j=1;j<=i;j++)
{
cin
>>D[i][j];
}
}

for(int i =1 ;i<=n;++i)
{
maxSum[n][i]
= D[n][i];
}

for(int i = n-1;i>=1;--i)
{
for(int j=1;j<=i;++j)
{
maxSum[i][j]
= max(maxSum[i+1][j],maxSum[i+1][j+1])+D[i][j];
}
}
cout
<< maxSum[1][1]<<endl;

return 0;
}

 进一步的,直接用一维数组存放每次计算后得到的值,得到简化后的递推代码如下:

#include "stdafx.h"
#include
<iostream>
#include
<algorithm>

using namespace std;

#define MAX 101
int D[MAX][MAX];
int n;
int maxSum[MAX];

int _tmain(int argc, _TCHAR* argv[])
{
int i,j;
cin
>>n;

for(int i=1;i<=n;i++)
{
for(int j=1;j<=i;j++)
{
cin
>>D[i][j];
}
}

for(int i =1 ;i<=n;++i)
{
maxSum[i]
= D[n][i];
}

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
<< maxSum[1]<<endl;

return 0;
}

 

运行结果示例:

动态规划——数字三角形