目录

数字三角形

摘花生 

 最低通行费

方格取数 

 传纸条

来源：898. 数字三角形 - AcWing题库

给定一个如下图所示的数字三角形，从顶部出发，在每一结点可以选择移动至其左下方的结点或移动至其右下方的结点，一直走到底层，要求找出一条路径，使路径上的数字的和最大。

        7
      3   8
    8   1   0
  2   7   4   4
4   5   2   6   5

输入格式

第一行包含整数 nn，表示数字三角形的层数。

接下来 nn 行，每行包含若干整数，其中第 ii 行表示数字三角形第 ii 层包含的整数。

输出格式

输出一个整数，表示最大的路径数字和。

数据范围

1≤n≤5001≤n≤500,
−10000≤三角形中的整数≤10000−10000≤三角形中的整数≤10000

输入样例：

5
7
3 8
8 1 0 
2 7 4 4
4 5 2 6 5

输出样例：

30

 思路：

dp问题最重要的是：怎么表示其状态，怎么确定其转移方程。

状态表示：dp[i][j]:表示从初始位置（1,1）走到当前位置（i,j）所经过的最大路径和。

属性：max.

状态转移方程：dp[i][j]=max(dp[i-1][j-1],dp[i-1][j])+a[i][j];

dp[i-1][j-1]表示从左上做到当前位置，dp[i-1][j]表示从上面一行走到当前位置，两个之中取最大的一个。

#include
using namespace std;
const int N=510;
int a[N][N];int dp[N][N];
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    for(int j=1;j<=i;j++)
    cin>>a[i][j];
    memset(dp,-0x3f,sizeof(dp));//保证dp原来的值不影响结果，也就是在进行判定是不会取。
    dp[1][1]=a[1][1];//初始化
    for(int i=2;i<=n;i++)
    {
        for(int j=1;j<=i;j++)
        {
            dp[i][j]=max(dp[i-1][j-1],dp[i-1][j])+a[i][j];
        }
    }
//在最后一行中进行搜索，取其中的最大值。
    int ret=-0x3f3f3f3f;
    for(int i=1;i<=n;i++)
    {
        ret=max(ret,dp[n][i]);
    }
    cout< 
摘花生  
来源：1015. 摘花生 - AcWing题库
 
Hello Kitty想摘点花生送给她喜欢的米老鼠。
 
她来到一片有网格状道路的矩形花生地(如下图)，从西北角进去，东南角出来。
 
地里每个道路的交叉点上都有种着一株花生苗，上面有若干颗花生，经过一株花生苗就能摘走该它上面所有的花生。
 
Hello Kitty只能向东或向南走，不能向西或向北走。
 
问Hello Kitty最多能够摘到多少颗花生。
 
 
输入格式
 
第一行是一个整数T，代表一共有多少组数据。
 
接下来是T组数据。
 
每组数据的第一行是两个整数，分别代表花生苗的行数R和列数 C。
 
每组数据的接下来R行数据，从北向南依次描述每行花生苗的情况。每行数据有C个整数，按从西向东的顺序描述了该行每株花生苗上的花生数目M。
 
输出格式
 
对每组输入数据，输出一行，内容为Hello Kitty能摘到得最多的花生颗数。
 
数据范围
 
1≤T≤1001≤T≤100,
 1≤R,C≤1001≤R,C≤100,
 0≤M≤10000≤M≤1000
 
输入样例：
 
2
2 2
1 1
3 4
2 3
2 3 4
1 6 5
 
输出样例：
 
8
16
 
思路：
 
与上面基本相同，这里就写一个大概。
 
状态表示：dp[i][j]:表示从左上角走到当前位置最多摘到的花生。
 
状态转移：dp[i][j]=max(dp[i-1][j],dp[i][j-1])+a[i][j];
 
#include
using namespace std;
const int N=110;
int a[N][N];
int dp[N][N];
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n;int m;
        scanf("%d%d",&n,&m);
        memset(dp,0,sizeof(dp));
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                scanf("%d",&a[i][j]);
            }
        }
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                dp[i][j]=max(dp[i-1][j],dp[i][j-1])+a[i][j];//状态转移方程。
            }
        }
        printf("%dn",dp[n][m]);
    }
    return 0;
}
 
 最低通行费 
一个商人穿过一个 N×NN×N 的正方形的网格，去参加一个非常重要的商务活动。
 
他要从网格的左上角进，右下角出。
 
每穿越中间 11 个小方格，都要花费 11 个单位时间。
 
商人必须在 (2N−1)(2N−1) 个单位时间穿越出去。
 
而在经过中间的每个小方格时，都需要缴纳一定的费用。
 
这个商人期望在规定时间内用最少费用穿越出去。
 
请问至少需要多少费用？
 
注意：不能对角穿越各个小方格（即，只能向上下左右四个方向移动且不能离开网格）。
 
输入格式
 
第一行是一个整数，表示正方形的宽度 NN。
 
后面 NN 行，每行 NN 个不大于 100100 的正整数，为网格上每个小方格的费用。
 
输出格式
 
输出一个整数，表示至少需要的费用。
 
数据范围
 
1≤N≤1001≤N≤100
 
输入样例：
 
5
1  4  6  8  10
2  5  7  15 17
6  8  9  18 20
10 11 12 19 21
20 23 25 29 33
 
输出样例：
 
109
 
样例解释
 
样例中，最小值为 109=1+2+5+7+9+12+19+21+33109=1+2+5+7+9+12+19+21+33。
 
思路：
 
属性：min
 
状态表示：dp[i][j]:表示从左上角走到当前位置的最小花费。
 
转态转移：dp[i][j]=min(dp[i-1][j],dp[i][j-1])+a[i][j];
 
#include
using namespace std;

const int N=110;
int a[N][N];
int dp[N][N];

int main()
{
	int n;int m;
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			scanf("%d",&a[i][j]);
		}
	}
	memset(dp,0x3f,sizeof(dp));
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			if(i==1&&j==1)
			dp[i][j]=a[i][j];
			else
			dp[i][j]=min(dp[i-1][j],dp[i][j-1])+a[i][j]; 
		}
	}
	printf("%dn",dp[n][n]);
	return 0;
} 
 
方格取数  
设有 N×N 的方格图，我们在其中的某些方格中填入正整数，而其它的方格中则放入数字0。如下图所示：
 
 
某人从图中的左上角 A 出发，可以向下行走，也可以向右行走，直到到达右下角的 B 点。
 
在走过的路上，他可以取走方格中的数（取走后的方格中将变为数字0）。
 
此人从 A 点到 B 点共走了两次，试找出两条这样的路径，使得取得的数字和为最大。
 
输入格式
 
第一行为一个整数N，表示 N×N 的方格图。
 
接下来的每行有三个整数，第一个为行号数，第二个为列号数，第三个为在该行、该列上所放的数。
 
行和列编号从 11 开始。
 
一行“0 0 0”表示结束。
 
输出格式
 
输出一个整数，表示两条路径上取得的最大的和。
 
数据范围
 
N≤10N≤10
 
输入样例：
 
8
2 3 13
2 6 6
3 5 7
4 4 14
5 2 21
5 6 4
6 3 15
7 2 14
0 0 0
 
输出样例：
 
67
 
 思路：
 
这道题可能会有人这样想：因为这里是要走两次，所以可以用动态规划从左上角到右下角，将走到的点置为零，然后再走一边。其实这里犯了一个错误，没有考虑动态规划的无后效性，在第一次走过之后，第一次的走的方式会影响第二次的走的方式。
 
正确的解题方式：一起走
 
状态表示：dp[k][i][j]:表示走了k步，一个人走到（i,k-i）位置，另一个人走到（j,k-j）位置的最大值。注意：i,j都表示横坐标。
 
走法就可以分为：下下,下右,右下，右右，这四种。
 
状态转移为：
 
                     dp[k][i1][i2] = max(dp[k][i1][i2],dp[k-1][i1-1][i2-1] + w);  //下下
                      dp[k][i1][i2] = max(dp[k][i1][i2],dp[k-1][i1-1][i2] + w);  //下右 
                      dp[k][i1][i2] = max(dp[k][i1][i2],dp[k-1][i1][i2-1] + w);  //右下
                      dp[k][i1][i2] = max(dp[k][i1][i2],dp[k-1][i1][i2] + w);  //右右 
 
#include
using namespace std;
const int N=15;
int g[N][N];
int dp[N*2][N][N];
int main()
{
	int n;
	scanf("%d",&n);
	int w,v,s;
	while(scanf("%d%d%d",&w,&v,&s)!=EOF)
	{
		if(w==0&&v==0&&s==0)
		break;
		g[w][v]=s;
	} 
	int t;
	for(int k=2;k<=2*n;k++)//为一个人走的步数，两个人的步数一样。 
	{
		for(int i=1;i<=n;i++)
		{
			for(int i2=1;i2<=n;i2++)
			{
				int j=k-i;int j2=k-i2;
				if(j>=1&&j<=n&&j2>=1&&j2<=n)//注意边界问题 
				{
				t=g[i][j];//考虑到两者相交的状况，因为步数k相同，所以如果i==i2,那么列数也相
//同，所以坐标相同。
				if(i!=i2) t+=g[i2][j2];
				dp[k][i][i2]=max(dp[k][i][i2],dp[k-1][i][i2]+t);
				dp[k][i][i2]=max(dp[k][i][i2],dp[k-1][i-1][i2]+t);
				dp[k][i][i2]=max(dp[k][i][i2],dp[k-1][i][i2-1]+t);
				dp[k][i][i2]=max(dp[k][i][i2],dp[k-1][i-1][i2-1]+t);
				}
			}
		}
	}
	printf("%dn",dp[n*2][n][n]);
	return 0;
} 
 
 传纸条 
小渊和小轩是好朋友也是同班同学，他们在一起总有谈不完的话题。
 
一次素质拓展活动中，班上同学安排坐成一个 mm 行 nn 列的矩阵，而小渊和小轩被安排在矩阵对角线的两端，因此，他们就无法直接交谈了。
 
幸运的是，他们可以通过传纸条来进行交流。
 
纸条要经由许多同学传到对方手里，小渊坐在矩阵的左上角，坐标 (1,1)(1,1)，小轩坐在矩阵的右下角，坐标 (m,n)(m,n)。
 
从小渊传到小轩的纸条只可以向下或者向右传递，从小轩传给小渊的纸条只可以向上或者向左传递。 
 
在活动进行中，小渊希望给小轩传递一张纸条，同时希望小轩给他回复。
 
班里每个同学都可以帮他们传递，但只会帮他们一次，也就是说如果此人在小渊递给小轩纸条的时候帮忙，那么在小轩递给小渊的时候就不会再帮忙，反之亦然。 
 
还有一件事情需要注意，全班每个同学愿意帮忙的好感度有高有低（注意：小渊和小轩的好心程度没有定义，输入时用 00 表示），可以用一个 0∼1000∼100 的自然数来表示，数越大表示越好心。
 
小渊和小轩希望尽可能找好心程度高的同学来帮忙传纸条，即找到来回两条传递路径，使得这两条路径上同学的好心程度之和最大。
 
现在，请你帮助小渊和小轩找到这样的两条路径。
 
输入格式
 
第一行有 22 个用空格隔开的整数 mm 和 nn，表示学生矩阵有 mm 行 nn 列。
 
接下来的 mm 行是一个 m×nm×n 的矩阵，矩阵中第 ii 行 jj 列的整数表示坐在第 ii 行 jj 列的学生的好心程度，每行的 nn 个整数之间用空格隔开。
 
输出格式
 
输出一个整数，表示来回两条路上参与传递纸条的学生的好心程度之和的最大值。
 
数据范围
 
1≤n,m≤501≤n,m≤50
 
输入样例：
 
3 3
0 3 9
2 8 5
5 7 0
 
输出样例：
 
34
 
思路：
 
这道题与上面那个方格取数是一样的，虽然题目要求的是从左上角走到右下角，但是我们可以看成与方格取数一样，从左上角同时走。
 
属性：max.
 
状态表示：dp[k][i1][12]:表示走了k步，一个横坐标为i1,另一个横坐标为i2时的最大好心值。
 
状态转移：基本与方格取数一样，分为下下,下右,右下，右右。
 
dp[k][i1][i2]=max(dp[k-1][i1][12]+t,dp[k][i1][i2]);//右右
 
dp[k][i1][i2]=max(dp[k-1][i1-1][12]+t,dp[k][i1][i2]);//下右
 
dp[k][i1][i2]=max(dp[k-1][i1-1][12-1]+t,dp[k][i1][i2]);//下下
 
dp[k][i1][i2]=max(dp[k-1][i1][12-1]+t,dp[k][i1][i2]);//右下
 
#include
#include
#include
#include
using namespace std;
const int N=55;
int g[N][N];
int dp[N*2][N][N];
int n;int m;
int main()
{
   int n;int m;
   cin >> n >> m;
   for(int i=1;i<=n;i++)
   {
       for(int j=1;j<=m;j++)
       {
           cin >> g[i][j];
       }
   }
   for(int i=2;i<=n+m;i++)//枚举走的步数。
   {
       for(int j1=1;j1<=n;j1++)
       {
           for(int j2=1;j2<=n;j2++)
           {
              int k1=i-j1;int k2=i-j2;//每一个的纵坐标。
              if(k1>=1&&k1<=m&&k2>=1&&k2<=m)
              {
                  int t=g[j1][k1];//当横坐标相同时，表示两者走到了同一个方格，只用取一次。
                  if(j1!=j2)
                  t+=g[j2][k2];
                  dp[i][j1][j2]=max(dp[i-1][j1-1][j2]+t,dp[i][j1][j2]);
                  dp[i][j1][j2]=max(dp[i-1][j1-1][j2-1]+t,dp[i][j1][j2]);
                  dp[i][j1][j2]=max(dp[i-1][j1][j2-1]+t,dp[i][j1][j2]);
                  dp[i][j1][j2]=max(dp[i-1][j1][j2]+t,dp[i][j1][j2]);
              }
           }
       }
   }
   cout<