数字三角形两种dp思路分析
思路1 : 从上到下想 –> 正常思路
采用闫氏dp分析法分析
|集合 : 从起点(1,1) 到 第i行j列的方案
|
|
|--------f(i,j)状态表示----|
| |
| |
| |属性 : 集合中可行方案中的最大值 max
DP
|
|
|
|
|----------状态计算 : 根据集合划分,将一个大集合划分为若干个子集,
设我们要求解f(i,j), 然后来尝试将其分为更小的集合
观察发现到达 f(i,j) 这个点的路径可以分为两类子集,一类是从其左上来的,一类是从其右上来的集合,即在
左上和右上都存在的情况下 f(i,j) = max(f(i-1. j-1), f(i - 1, j)) + 本身的值。 故代码如下
#include<iostream>
using namespace std;
constexpr int INF = 1e+9;
constexpr int N = 510;
int n;
int a[N][N];
auto main() -> int
{
cin >> n;
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= i; ++j) cin >> a[i][j];
for(int i = 2; i <= n; ++i)
{
for(int j = 1; j <= i; ++j)
{
if(j == 1) a[i][j] += a[i - 1][j]; // 两种特判,只有左上和只有右上的情况
else if(j == i) a[i][j] += a[i - 1][j - 1]; // 当然这里的特判可以给每一行的左右两边的边界都赋值为 - INF 也可
else a[i][j] += max(a[i - 1][j], a[i - 1][j - 1]);
}
}
int res = -INF;
for(int i = 1; i <= n; ++i) res = max(res, a[n][i]); // 然后遍历最后的一行, 找出最大的
cout << res << endl;
return 0;
}
思路2 : 从下到上分析
由于从上到下写状态转移方程的时候,左上和右上还要特判考虑情况,如果我们从下面开始分析
|集合 : 从最下面的一行 到 第i行j列的方案 (此时集合含义与上面不同,并不是从起点出发,而是从最下面一行的某个出发)
|
|
|--------f(i,j)状态表示----|
| |
| |
| |属性 : 集合中可行方案中的最大值 max
DP
|
|
|
|
|----------状态计算 : 根据集合划分,将一个大集合划分为若干个子集,
设我们要求解f(i,j), 然后来尝试将其分为更小的集合
这里从倒数第二行开始分析,因为倒数第一行本身就是最后一行。 故对于到达 f(i,j) 的集合这里分为两大子集, 一类子集是从左下到到达的,另一条是从右下到达的
且从倒数第二行开始,无论何种情况,这两类子集都存在。 故写出我们的代码如下:
#include<iostream>
using namespace std;
constexpr int N = 510;
int n;
int arr[N][N];
auto main() -> int
{
cin >> n;
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= i; ++j) cin >> arr[i][j];
for(int i = n - 1; i >= 1; --i)
{
for(int j = 1; j <= i; ++j)
arr[i][j] += max(arr[i+1][j], arr[i+1][j+1]);
}
cout << arr[1][1] << endl; // 题目最后要求的就是从顶部1,1出发到达底层使得路径上的数字之和最大
// f[1][1]根据我们状态表示的含义就是从最下面一行到达1行1列方案中数字和最大的值
return 0;
}