本文共 1974 字，大约阅读时间需要 6 分钟。

73   88   1   02   7   4   44   5   2   6   5(Figure 1)Figure 1 shows a number triangle. Write a program that calculates the highest sum of numbers passed on a route that starts at the top and ends somewhere on the base. Each step can go either diagonally down to the left or diagonally down to the right.

Input

Your program is to read from standard input. The first line contains one integer N: the number of rows in the triangle. The following N lines describe the data of the triangle. The number of rows in the triangle is > 1 but <= 100. The numbers in the triangle, all integers, are between 0 and 99. Output Your program is to write to standard output. The highest sum is written as an integer. Sample Input

573 88 1 0 2 7 4 44 5 2 6 5

Sample Output

30

大体思路：

这大概是最简单的DP题了把，其实直接用递归暴力解也能算出答案，但多出了太多没有必要的重复计算。所以需要DP来简化操作    而简化操作则分为两个方法，分别对应递归和递推

递归代码：

#include
   
    #include
    
     #include
     
      #include
      
       using namespace std;int a[100][100];int maxsum[100][100];//简化计算部分，将计算过的每次结果进行记录，从而减少计算量int Dp(int i,int j,int n){    if(i==n-1)        return a[i][j];    if(maxsum[i][j]==-1)        maxsum[i][j]=a[i][j]+max(Dp(i+1,j,n),Dp(i+1,j+1,n));    return maxsum[i][j];}int main(){    //freopen("in.txt","r",stdin);    int n;    while(cin>>n)    {        memset(maxsum,-1,sizeof(maxsum));        for(int i=0;i
       
        >a[i][j];        cout<
        
         <
        
       
      
     
    
   

递推代码：

与递归不同，递归的想法是从最底层进行计算，每层的最优结果放在一个一维数组里。得出最后的结果。

#include
   
    #include
    
     #include
     
      #include
      
       using namespace std;int main(){    int n,a[100][100];    while(cin>>n)    {        for(int i=0;i
       
        >a[i][j];        int maxsum[100];//滚动数组，记录最有结果，        for(int i=n-1;i>=0;--i){            for(int j=0;j<=i;++j){                if(i==n-1)                    maxsum[j]=a[i][j];                else                    maxsum[j]=a[i][j]+max(maxsum[j],maxsum[j+1]);            }//覆盖掉上一次的计算结果，因为没有用了。        }        cout<
        
         <
        
       
      
     
    
   

转载地址：https://blog.csdn.net/SCaryon/article/details/60151577 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！