数字三角形
-
核心思想：线性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;}
-
-
