数字金字塔

id: number_pyramid

数学金字塔

说明

本节内容的前置知识为

  • 集合
    • 集合分成不重不漏的子集
  • 组合数学

题目描述

观察下面的数字金字塔。

写一个程序来查找从最高点到底部任意处结束的路径，使路径经过数字的和最大。每一步可以走到左下方的点也可以到达右下方的点。

TODO

搜索1 : 枚举

这里采用最朴素,最简单的想法,类似走迷宫(TODO)的思路: 枚举出所有可能的路线,找出所有路线中值最大的.

如何枚举所有可能的路线呢?我们想像有一个人在金字塔上行走,在某一时刻,他处于(x,y)(x,y)这个点,那么(x,y)(x,y)这个坐标值就是这个人的状态,下一个时刻,他可能走1.(x+1,y)(x+1,y),2.(x+1,y+1)(x+1,y+1)这两个点,如果走到了边界x=nx = n,那他就回溯,所以我们使用递归法,记录所走过的路径,就可以求出所有可能走的路线的线路了.

点击 
//Author by [Rainboy](https://github.com/rainboylvx) 
//date: 2024-06-01 17:48:24
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e3+5;
int n,m;
int a[maxn][maxn];
int rcd[maxn]; //记录走过的点的值
int ans;
int cnt;

void dfs(int x,int y) {
    //记录下来这个点
    rcd[x] = a[x][y]; 

    //到达边界
    if( x == n) {
        int sum = 0;
        cnt++;
        // cout << cnt << " : ";
        //求走过的点的和
        for(int i = 1;i <= n ;++i ) // i: 1->n
        {
            sum += rcd[i];
            // cout << rcd[i] << " ";
        }
        // std::cout << "\n";
        //记录最大值
        if( ans < sum) ans = sum;
        return ;
    }
    //向左走
    dfs(x+1,y);
    //向右走
    dfs(x+1,y+1);
}

int main (int argc, char *argv[]) {
    std::cin >> n;
    for(int i = 1;i <= n ;++i ) // i: 1->n
    {
        for(int j = 1;j <= i ;++j ) // j: 1->i
        {
            cin >> a[i][j];
        }
    }
    dfs(1,1);
    std::cout << ans << "\n";

    return 0;
}

算法的时间同样为2n−12^{n-1}.面对最大数据10001000时会超时.

搜索2 : 小朋友法,列公式

设f(i,j)f(i,j)表示从点(i,j)(i,j)开始向下走到最后一层能得到的最大值.

于是我们得到了一个推导公式

f(i,j)={max(f(i+1,j),f(i+1,j+1))+a[i][j]i!=na[i][j]i==n(a) f(i,j) = \left\{ \begin{array}{cc} max(f(i+1,j),f(i+1,j+1)) + a[i][j] & i != n\\ a[i][j] & i == n \end{array} \right. \tag a

如果这样思考,就类似于: 处于点(x,y)(x,y)的小朋友,去询问(x+1,y),(x+1,y+1)(x+1,y),(x+1,y+1)的小朋友: 从他们所在的坐标开始走能得到的最大值是什么.

点击 
#include <iostream>
using namespace std;

const int maxn = 1005;
int n;
int a[maxn][maxn];


//dfs(x,y)
int dfs(int x,int y) {
    //边界,最后一行
    if( x == n) return a[x][y];

    //向左走的最大值
    int t1 = dfs(x+1,y);
    //向右走的最大值
    int t2 = dfs(x+1,y+1);

    // t1 变成两者之间的最大的那个
    if( t1 < t2) t1 = t2;

    // 加上x,y这个点的值
    return a[x][y] + t1;

}

int main () {
    cin >> n;
    //读取数据
    for(int i=1;i<=n;i++) {
        for(int j =1;j<=i;j++)
            cin >> a[i][j];
    }

    int ans = dfs(1,1);
    cout << ans << endl;

    return 0;
}

算法的时间同样为2n−12^{n-1}.面对最大数据10001000时会超时.

记忆化优化

为什么dfs要比dp慢那么呢?因为dfs为重复的计算子问题

TODO : 详细的讲一下:

#include <iostream>
using namespace std;

const int maxn = 1005;
int n;

int a[maxn][maxn];
// f[i][j] 就表示从(i,j)向下走的最大值
int f[maxn][maxn]; 


//dfs(x,y)
int dfs(int x,int y) {
  if( x == n) return a[x][y];
  if( f[x][y] != -1) return f[x][y];

  int t1 = dfs(x+1,y);
  int t2 = dfs(x+1,y+1);

  if( t1 < t2) t1 = t2;

  f[x][y] = a[x][y] + t1;
  return f[x][y];

}

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

  for(int i =0;i<maxn;i++)
  for(int j =0;j<maxn;j++)
    f[i][j] = -1;
  /* memset() */

  int ans = dfs(1,1);
  cout << ans << endl;

  return 0;
}

dp来做

考虑到分解子问题的f(i,j)f(i,j)

那么到达(i,j)(i,j)的下一个点的值f(i+1,j),f(i+1,j+1)f(i+1,j),f(i+1,j+1)的值是固定的

如果可以得到先得到第i+1i+1层的所有的ff值,那不就可以直接使用`for循环得到第ii层的所有的值了吗?

TODO : 图

显然我可以轻松的得到最后一层的ff值,因为最一层不需要再向下走了,可以想像成只有一层的金字塔.

f(i,j)=a[i][j]i是最后一层,i==n f(i,j) = a[i][j] \text{i是最后一层},i == n

于是可以想到,

  1. 先得到最后一层,也就是第n层
  2. 然后利用第n层的值,得到第n−1n-1层的值
  3. …
  4. 利用第22层的值,得到第11层的值 我们手动的推导一遍

于是我们就是原来的由上到下(大问题分解子问题)的dfs,变成了由下到上(子问题推出大问题)的dp

代码

//Author by [Rainboy](https://github.com/rainboylvx) 
//date: 2024-06-01 17:48:24
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e3+5;
int n,m;
int a[maxn][maxn];
//f[i][j] 表示从(i,j)向下走,能得到的最大值
int f[maxn][maxn];
int ans;
int cnt;


int main (int argc, char *argv[]) {
    std::cin >> n;
    for(int i = 1;i <= n ;++i ) // i: 1->n
    {
        for(int j = 1;j <= i ;++j ) // j: 1->i
        {
            cin >> a[i][j];
        }
    }
    for(int i = 1;i <= n ;++i ) // i: 1->n
    {
        //初始化最后一层的数据,边界
        f[n][i] = a[n][i];
    }

    //层数倒过来
    for(int i=n-1;i>=1;i--){
        //处理这一层的所有的值
        for(int j = 1;j <=i;j++)
            f[i][j] = max(f[i+1][j+1],f[i+1][j]) + a[i][j];
    }
    //输出答案
    cout << f[1][1] << endl;

    return 0;
}

集合

从集合的角度思考问题

结论,本质上来说,dp就是集合的分解

DP之间的关系:如何从A集合得到B集合

DP相关概念

阶段: 就是上面描述的层.

练习题目