题目描述

数字三角形

若一共有n层，则要搜索2^(n-1)次（因为每一层向左向右有两种选择）

对于路径问题（一类问题），通常可以用点的坐标来表示

从集合的角度来分析

考虑从上往下的方向还是从下往上的方向

若是从上往下：
（1）左右两边要比较
（2）要考虑边界问题，加入特判

若是从下往上：不需要考虑边界，不用写特判

Dp：每次处理一类问题（一个集合）
暴力搜索：每次处理一个问题

C++ 代码

#include<iostream>
#include<algorithm>
#include<string>

using namespace std;
const int N=510;

int n;
int w[N][N];    //存原三角形中的值
int f[N][N];    //存路径状态的值

int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=i;j++)
        {
            cin>>f[i][j];           //走到每个点的长度（读入三角形矩阵）
        }
    }
   // for(int i=1;i<=n;i++)f[n][i]=w[n][i];   //初始化边界    矩阵中：f[n][1]~f[n][n]

    for(int i=n-1;i;i--)       //从倒数第二层开始
    {
        for(int j=1;j<=i;j++)
        {
            f[i][j]+=max(f[i+1][j],f[i+1][j+1]);   //相当于先两两比较出较大的，然后加到上一层的点上，如此循环
        }
    }
    cout<<f[1][1]<<endl;  //从最下方走到最上面的点的路径的最大值
    return 0;
}