题目描述

给定一个如下图所示的数字三角形，从顶部出发，在每一结点可以选择移动至其左下方的结点或移动至其右下方的结点，一直走到底层，要求找出一条路径，使路径上的数字的和最大。

        7
      3   8
    8   1   0
  2   7   4   4
4   5   2   6   5

输入格式

第一行包含整数n，表示数字三角形的层数。

接下来n行，每行包含若干整数，其中第 i 行表示数字三角形第 i 层包含的整数。

输出格式

输出一个整数，表示最大的路径数字和。

数据范围

$1≤n≤500$,
$−10000≤三角形中的整数≤10000$

输入样例：

5
7
3 8
8 1 0 
2 7 4 4
4 5 2 6 5

输出样例：

30

做题思路

从后往前想：
1. 这个点是从左下上来的， 还是从右下上来的
2. 即然， f[i][j]: 自下向上 到达 f[i][j]的路径最大值。 那么最下方的一排数 就保持原来的w数组的不变。

C++代码

#include<bits/stdc++.h>

using namespace std;

const int N = 510;
int n;
int w[N][N];  // 原三角形数。
int f[N][N];  //f[i][j]: 自下向上 到达 f[i][j]的路径最大值
int main()
{ 
    cin>>n;

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

    for(int j=1;j<=n;j++)
        f[n][j] = w[n][j];  // 对三角形最底层的数 初始化

    for(int i=n-1;i;i--)
        for(int j=1;j<=i;j++)
            f[i][j]=max(f[i+1][j]+w[i][j],f[i+1][j+1]+w[i][j]);   //自下向上推

    cout<<f[1][1]<<endl;


    return 0;
}

java代码

import java.util.Scanner;

public class Main{        

    final static int N=510;
    static int n;
    static int w[][]= new int [N][N];
   static int f[][]= new int [N][N];


    public static void main(String []args){

        Scanner cin = new Scanner(System.in);
        n = cin.nextInt();

    for(int i=1;i<=n;i++)
        for(int j=1;j<=i;j++)
            w[i][j]= cin.nextInt();  

    for(int j=1;j<=n;j++)
        f[n][j] = w[n][j];  // 对三角形最底层的数 初始化

    for(int i=n-1;i>=0;i--)
        for(int j=1;j<=i;j++)
            f[i][j]=Math.max(f[i+1][j]+w[i][j],f[i+1][j+1]+w[i][j]);   //自下向上推

 //   cout<<f[1][1]<<endl;
        System.out.println(f[1][1]);

    }
}