数字三角形
题目
给定一个如下图所示的数字三角形，从顶部出发，在每一结点可以选择移动至其左下方的结点或移动至其右下方的结点，一直走到底层，要求找出一条路径，使路径上的数字的和最大。
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5输入样例：
5 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5
输出样例
30
图解
转移方程
f[i][j] = max(f[i - 1][j - 1],f[i - 1][j]) + a[i][j]
参考代码
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 510,INF = 0x3f3f3f3f;
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]);
//因为数据可能为负，在判断最大值的时候要将f初始化
for(int i = 0; i <= n ; i ++)
for(int j = 0; j <= n; j ++)
f[i][j] = -INF;
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] + a[i][j], f[i - 1][j - 1] + a[i][j]);
int res = 0;
//枚举最后一行的最大值
for(int i = 1; i <= n; i ++) res = max(res,f[n][i]);
printf("%d",res);
return 0;
} 原题链接
数字三角形以及它所扩展的题目
摘花生(原题链接)
大致思路是给你一个矩阵，你从(0,0)走到(n,m)，每次取出格子里面的值，要保证到达(n,m)是全局最大的。
例如2 × 3 的矩阵：
我们很惊奇的发现，这个题和数字三角形很像，数字三角形的走的方式是左下角或者右下角，本题走的方式是往下和往右走！
图解
转移方程
f[i][j] = max(f[i - 1][j] , f[i][j - 1]) + a[i][j]
代码
#include <algorithm>
#include <stdio.h>
#include <iostream>
using namespace std;
const int N = 110;
int a[N][N],f[N][N];
int r,c;
int main()
{
int T;
scanf("%d",&T);
while(T --)
{
scanf("%d%d",&r,&c);
for(int i = 1; i <= r; i ++)
for(int j =1 ; j <= c; j ++)
scanf("%d",&a[i][j]);
f[1][1] = a[1][1];
for(int i = 1; i <= r;i ++)
for(int j = 1; j <= c; j ++)
f[i][j] = max(f[i - 1][j],f[i][j -1] ) + a[i][j];
printf("%d\n",f[r][c]);
}
} 最低通行费(题目链接)
大致意思是你要从一个矩阵的最开始的位置(1,1)走到(n,n)，每次走过一个格子都有一个花费，要你在2n - 1步走到终点，且花费之和最小。
分析
咋一看和上面摘花生的题很像哎，只是这个是求最小值而且只能走2n - 1 步，其实这里的2n - 1 步就完全可以推出我们只能往下或者往右走，如果你往回走（指的上和左）走的话，那么你是无法达到(n,n)这个点的，所以这个题就是上一道的变形，只是我们需要求的是最小值。
大家画一下图就能够理解
图解
代码
#include <algorithm>
#include <iostream>
#include <cstring>
#include <stdio.h>
using namespace std;
const int N = 110,INF = 0x3f3f3f3f;
int f[N][N],w[N][N];
int n;
int main()
{
scanf("%d",&n);
for(int i = 1; i <= n; i ++)
for(int j = 1; j <= n; j ++)
scanf("%d",&w[i][j]);
memset(f,0x3f,sizeof f); //因为要求最小值所有要将状态都置为一个很大的数
f[1][1] = w[1][1]; //第一个格子是起点一定要选
for(int i = 1; i <= n; i ++)
for(int j = 1; j <= n; j ++)
{
if(i > 1 || j > 1)
f[i][j] = min(f[i - 1][j], f[i][j - 1]) + w[i][j]; //第一行不能从上边转移过来，第一列不能从左边转移过来
}
printf("%d",f[n][n]);
} 方格取数(题目链接)
题目意思从(1,1)走到(n,n)，一共走两次，每次走过的路径上格子的值都会被置为0，求最大值。
分析
该题做法有很多种，我们这里采用动态规划来做，我们可以从上面的题来类推一下
f[i][j] = max(f[i - 1][j] , f[i][j - 1]) + a[i][j] //这是走一次的做法
那么走两次那么就是
f[i1,j1,i2,j2]表示从(1,1),(1,1)走到（i1,j1),(i2,j2)的路径的最大值 那么我们怎么去解决"两个格子被重复选择" i1 == i2 && j1 == j2就可以确定他们是同一个格子 我们这里将上述式子做一个等价变形 i1 + j1 == i2 + j2 && i1 == i2 意思是：如果两个格子相等那么他们走的步数也一定相等 那么此时我们可以做一个优化，将4维状态装换成3维：f[k][i1][i2] k表示的是：一个格子的横纵坐标之和 i1表示的是：第一条路径的横坐标，i2表示的是：第二条路径的横坐标 那么第一条路径的纵坐标就是:k - i1，第二条路径的纵坐标就是：k - i2
示意图：
图解
参考代码
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 15;
int f[N * 2][N][N],w[N][N];
int n;
int main()
{
scanf("%d",&n);
int a,b,c;
while(cin >> a >> b >> c, a || b || c) w[a][b] = c;
for(int k = 2;k <= 2 * n; k ++)
for(int i1 = 1; i1 <= n; i1 ++)
for(int i2 = 1; i2 <= n; i2 ++)
{
int j1 = k - i1,j2 = k - i2;
if(j1 <= 0 || j2 <= 0 || j1 > n || j2 > n) continue;
f[k][i1][i2] = max(max(f[k - 1][i1][i2],f[k - 1][i1 - 1][i2 - 1]),max(f[k - 1][i1 - 1][i2],f[k - 1][i1][i2 - 1]));
if(i1 == i2) f[k][i1][i2] += w[i1][j1];
else f[k][i1][i2] += w[i1][j1] + w[i2][j2];
}
printf("%d",f[n * 2][n][n]);
} 1.
传纸条
传纸条的做法和方格取数的做法完全一致，只是读入数据不太一样。
参考代码
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 55;
int f[N * 2][N][N],w[N][N];
int n,m;
int main()
{
scanf("%d%d",&n,&m);
for(int i = 1; i <= n; i ++ )
for(int j = 1; j <= m; j ++)
scanf("%d",&w[i][j]);
for(int k = 2; k <= n + m; k ++)
for(int i1 = 1; i1 <= n;i1 ++)
for(int i2 = 1; i2 <= n; i2 ++)
{
int j1 = k - i1,j2 = k - i2;
if(j1 <= 0 || j1 > m || j2 <= 0 || j2 > m) continue;
f[k][i1][i2] = max(max(f[k - 1][i1][i2],f[k - 1][i1 - 1][i2 - 1]),max(f[k - 1][i1 - 1][i2],f[k - 1][i1][i2 - 1]));
if(i1 == i2) f[k][i1][i2] += w[i1][j1];
else f[k][i1][i2] += w[i1][j1] + w[i2][j2];
}
printf("%d",f[n + m][n][n]);
}
感谢各位聚聚阅读~
京公网安备 11010502036488号