P4736 数字金字塔2（基础）

解题思路

题目给出一座数字金字塔，从塔顶出发，每一步可以走到左下方的数字或右下方的数字，一直走到最下面一层的任意一个数字为止。我们要找一条路径，让经过的数字之和最小。

用动态规划来做。设 dp[i][j] 表示从塔顶走到第 i 行第 j 列时，路径上数字和的最小值。第 1 行只有塔顶一个数字，所以 dp[1][1] = a[1][1]。到了第 i 行第 j 列，它只能从上一行的正上方 (i-1,j) 或者左上方 (i-1,j-1) 走下来，为了让和最小，当然选择两者中较小的那个，再加上当前格子的数字，即 dp[i][j] = min(dp[i-1][j], dp[i-1][j-1]) + a[i][j]。这里要特别注意边界：每行最左边一列（j=1）只能从正上方 (i-1,1) 下来，最右边一列（j=i）只能从左上方 (i-1,i-1) 下来，这两种情况要单独处理。全部算完后，答案就是最后一行所有 dp[N][j] 里的最小值。

N 最大 1000，每个数字不超过 100，路径上最多 1000 个数字，最大和不超过 100000，用 long long 保存非常安全。因为数据量比较大（约 50 万个数字），用 scanf 快速读入。以样例为例，塔顶是 13，一路挑选最小的数字走，最小和是 49，与输出一致。

参考代码

// 数字金字塔2：从塔顶走到底部任意处，每次走左下方或右下方，求路径数字和的最小值
#include <cstdio>
int main(){
  static int a[1005][1005];        // 金字塔数字，大数组放全局区
  static long long dp[1005][1005]; // dp[i][j]：走到第i行第j列的最小和
  int n,i,j;
  long long ans,t;
  std::scanf("%d",&n);
  for(i=1;i<=n;i++)
    for(j=1;j<=i;j++)
      std::scanf("%d",&a[i][j]);
  dp[1][1]=a[1][1];                // 塔顶
  for(i=2;i<=n;i++){
    for(j=1;j<=i;j++){
      if(j==1) t=dp[i-1][1];               // 最左边只能从正上方来
      else if(j==i) t=dp[i-1][i-1];        // 最右边只能从左上方来
      else t=dp[i-1][j-1]<dp[i-1][j]?dp[i-1][j-1]:dp[i-1][j];
      dp[i][j]=t+a[i][j];
    }
  }
  ans=dp[n][1];                    // 答案在最后一行里取最小
  for(j=2;j<=n;j++) if(dp[n][j]<ans) ans=dp[n][j];
  std::printf("%lld\n",ans);
  return 0;
}

复杂度分析

金字塔一共约 N²/2 个数字，每读入并计算一个格子只需要常数时间，所以时间 O(N²)。空间上用两个 N×N 的数组，是 O(N²)。N=1000 时大约 100 万个格子，运行很快，内存也足够。