一、实践题目

数字三角形

 

二、问题描述

计算出从三角形的顶至底的一条路径，使该路径经过的数字总和最大。 

 

三、算法描述

描述：自底向上的将两行相加之和最大的数储存在数组中，最后dp[1][1]即为所求。

核心算法：dp[i][j]=max(dp[i+1][j],dp[i+1][j+1])+dp[i][j];

代码实现：

#include<iostream>

using namespace std;

int n;

int dp[109][109];

int main()

{

cin>>n;

for(int i=1;i<=n;i++)

for(int j=1;j<=i;j++)

{

cin>>dp[i][j];

}

for(int i=n-1;i>=0;i--)

for(int j=1;j<=i;j++)

{

dp[i][j]=max(dp[i+1][j],dp[i+1][j+1])+dp[i][j];

}

cout<<dp[1][1]<<endl;

return 0;

}

 

四、算法时间及空间复杂度分析

空间复杂度：O(n²) 三角形的值保存在二维数组中

时间复杂度：O(n²) 算法有两个for循环，时间复杂度最大为n²

 

五、心得体会

动态规划最重要的就是递归方程，着重解决这个方程更有利于实现算法。