Algorithm2.8 基础dp
[TOC]
基础dp
数字三角形
https://www.luogu.com.cn/problem/P1216
题目大意：给一个三角形矩阵，然后从上往下走，怎么才能走的总量最大。
1、// 上往下 => 初始化三角形的上边两条边
初始化：dp[i][0] = dp[i-1][0]+a[i][0], dp[i][i] = dp[i-1][i-1]+a[i][i];
状态转移方程：dp[i][j] = max(dp[i-1][j-1],dp[i-1][j])+a[i][j];
2、下往上 => 初始化最下边的那条边
初始化： dp[r-1][i] = a[r-1][i];
状态转移方程：dp[i][j] = max(dp[i+1][i], dp[i+1][i+1])+a[i][j];
#include <iostream>
using namespace std;
#define maxn 1005
int r, a[maxn][maxn], dp[maxn][maxn], ans = 0;
#include <cmath>
// 上往下 => 初始化三角形的上边两条边(dp[i][0] = dp[i-1][0]+a[i][0], dp[i][i] = dp[i-1][i-1]+a[i][i];)
// dp[i][j] = max(dp[i-1][j-1],dp[i-1][j])+a[i][j];
// 下往上 => 初始化最下边的那条边 dp[r-1][i] = a[r-1][i];
// dp[i][j] = max(dp[i+1][i], dp[i+1][i+1])+a[i][j];
int main() {
scanf("%d", &r);
for (int i = 0; i < r; ++i)
for (int j = 0; j < i + 1; ++j)
scanf("%d", &a[i][j]);
//init
for (int i = 0; i < r; ++i) dp[r-1][i] = a[r-1][i];
for (int i = r-2; i >= 0; --i)
for (int j = 0; j < i + 1; ++j)
dp[i][j] = max(dp[i+1][j], dp[i+1][j+1])+a[i][j];
printf("%d\n", dp[0][0]);
/*
* // init
dp[0][0] = a[0][0];
for (int i = 1; i < r; ++i)
dp[i][0] = dp[i-1][0]+a[i][0], dp[i][i] = dp[i-1][i-1]+a[i][i];
for (int i = 2; i < r; ++i)
for (int j = 1; j < i ; ++j)
dp[i][j] = max(dp[i-1][j-1],dp[i-1][j])+a[i][j];
for (int i = 0; i < r; ++i) ans = max(ans, dp[r-1][i]);
printf("%d\n", ans);
*/
return 0;
}
数字三角形变形
https://www.luogu.com.cn/problem/P1508
变形一：状态转移方程：由两条路变成了三条路
变形二：起点的限制：导致每一层可以搜索到的范围是不同的（根据外层回圈来限定内层的遍历范围）
#include <iostream>
using namespace std;
const int maxn = 205;
int n, m, a[maxn][maxn], f[maxn][maxn], ans;
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j)
scanf("%d", &a[i][j]);
for (int i = n; i >= 1; --i)
for (int j = max(1, (m+1)/2-(n-i+1)); j <= min(m, (m+1)/2+(n-i+1)); ++j)
f[i][j] = a[i][j] + max(max(f[i+1][j], f[i+1][j-1]), f[i+1][j+1]);
for (int i = 1; i <= m; ++i) ans = max(ans, f[1][i]);
printf("%d\n", ans);
return 0;
}