第三章实践心得

给定一个由 n行数字组成的数字三角形如下图所示。试设计一个算法，计算出从三角形 的顶至底的一条路径(每一步可沿左斜线向下或右斜线向下)，使该路径经过的数字总和最大。

2、算法描述：

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

for(j=1;j<=n;j++)
       dp[n][j]=a[n][j];
    for(i=n-1; i>=1; i--)
    {
     for(j=1; j<=i; j++)
     {
      dp[i][j]= a[i][j]+ max(dp[i+1][j], dp[i+1][j+1]);
     }
    }
    cout<<dp[1][1];

定义一个新数组dp[]来存放路径最长的总和，通过一个递归算法，自底向上，dp[n-1] = a[i][j]+ max(dp[i+1][j], dp[i+1][j+1])，最后dp[1][1]的值就是最大总和。

3、算法空间、时间复杂度分析：

该算法的最高阶是循环嵌套，因此时间复杂度为：n*(n-1）+(n-1)+......+2*1

O(n)=n*n;

空间复杂度为n*n;

4、心得体会：

本题算法是动态规划中的基础所以比较简单，但在上机的时候因为一开始设置的数组比较小导致结果一直出错，所以今后还是多注意一些语法问题。