算法基础之数字三角形

数字三角形

• 核心思想：线性dp

  • 集合的定义为 f[i][j] –> 到i j点的最大距离

  • 从下往上传值 父节点f[i][j] = max(f[i+1][j] , f[i+1][j+1]) + w[i][j]

  • 初始化最后一层 f = w

  • 

  •   #include <bits/stdc++.h>using namespace std;const int N = 510;int w[N][N],f[N][N];int n;int main(){cin >> n;for (int i = 1; i <= n; i++)for (int j = 1; j <= i; j++)cin >> w[i][j];for(int i=1;i<=n;i++) f[n][i] = w[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]) + w[i][j];  //左孩子和右孩子取最大 + 距离cout << f[1][1] << endl;}
    

  • 优化版:

    •   #include <bits/stdc++.h>using namespace std;const int N = 510;int f[N][N];int 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 = 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]) + f[i][j];//用完f[i][j]距上一层距离 就将其更新成距底部距离cout << f[1][1] << endl;}