实际为基础课第五章DP里线性DP第一题
$$
动态规划
\begin {cases}
状态表示 f(i, j)
\begin {cases}
集合:所有从起点走到(i, j)的路径\\\
属性:路径数字和最大
\end{cases}\\\
\\\
状态计算
\begin {cases}
分类
\begin {cases}
从左下方到达(i, j) & f(i+1, j) + s(i, j)\\\
从右下方到达(i, j) & f(i+1, j+1) + s(i, j)\\\
\end {cases} \\\
\\\
求解:两种可能求max
\end{cases}\\\
\end {cases}
$$
N = int(input())
# 这里我多开了一些dp的空间,这样可以简化初始化的问题
dp = [[0]*(N+1) for _ in range(N+2)]
s = [[0]]
for i in range(N):
a = list(map(int, input().split()))
s.append(a) #将图读进s里, s[i]即为第i个,s[i][j]即为 i项里的第j项数值大小为a
for i in range(N, 0, -1):
for j in range(i):
dp[i][j] = max(dp[i+1][j], dp[i+1][j+1])+s[i][j]
# dp[][]定义为路径数值和,遍历之前i层,j表示那一层的第j个数,每一遍遍历后就从s树往上上了一层
# DFS+记忆化搜索,每次保存最大值,题意只要最大值,就只把之前路径和加上再对前层的上层(即本层)的左右两种可能性进行大小比较,选择更大的一条路。
print(dp[1][0])
第二种 从上往下构造
$$
动态规划
\begin {cases}
状态表示 f(i, j)
\begin {cases}
集合:所有从起点走到(i, j)的路径\\\
属性:路径数字和最大
\end{cases}\\\
\\\
状态计算
\begin {cases}
分类
\begin {cases}
从左上方到达(i, j) & f(i-1, j-1) + s(i, j)\\\
从右上方到达(i, j) & f(i-1, j) + s(i, j)\\\
\end {cases} \\\
\\\
求解:两种可能求max
\end{cases}\\\
\end {cases}
$$
c++版代码
#include <iostream>
#include <cstring>
using namespace std;
const int N = 510, INF = 1e9;
int a[N][N], f[N][N];
int n;
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i ++)
for (int j = 1; j <= i; j ++)
scanf("%d", &a[i][j]);
memset(f, 0x8f, sizeof f); // 初始化为负无穷
f[1][1] = a[1][1];
for (int i = 2; i <= n; i ++)
for (int j = 1; j <= i; j ++)
f[i][j] = max(f[i-1][j-1], f[i-1][j]) + a[i][j];
int res = -INF;
for (int j = 1; j <= n; j ++)
res = max(res, f[n][j]);
printf("%d\n", res);
return 0;
}