动态规划之数字三角形模型

题目：1015. 摘花生

思路

很经典的动态规划问题。

定义：v[i][j]表示位置是i,j的花生数量，f[i][j]表示走到位置i,j所能获得的最大花生数量。
初始状态：f[1][1],目标状态：f[n][m]
状态转移：由于题目规定只能向东或者向南走，所以说明当前情况只能由两种情况更新得到。

由左边一个格子更新而来
由上边一个格子更新而来

状态转移：由于我们是要取最大值，所以我们对两种情况取最大的那个即可。
边界问题：有多个方法处理边界问题。在下面的代码会具体体现。

代码

二维数组——边界处理Ⅰ

#include<iostream>

using namespace std;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);

	int T;
	cin >> T;
	while (T--)
	{
		int n, m;
		cin >> n >> m;

		int v[110][110], f[110][110];
		for (int i = 0; i < n; i++)
			for (int j = 0; j < m; j++)
				cin >> v[i][j];
		f[0][0] = v[0][0];
		for (int i = 0; i < n; i++)
		{
			for (int j = 0; j < m; j++)
			{
				if (i == 0 and j == 0)
					continue;
				if (i == 0)
					f[i][j] = f[i][j - 1] + v[i][j];
				else if (j == 0)
					f[i][j] = f[i - 1][j] + v[i][j];
				else
					f[i][j] = max(f[i - 1][j], f[i][j - 1]) + v[i][j];

			}
		}
		cout << f[n - 1][m - 1] << endl;
	}
}

这里我们是从0开始读入的，所以边界处理起来就有点麻烦。在循环内部要进行特判。可能方便理解，但是代码写起来有些麻烦，不太推荐。

二维数组——边界处理Ⅱ

#include<iostream>
#include<cstring>

using namespace std;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);

	int T;
	cin >> T;
	while (T--)
	{
		int n, m;
		cin >> n >> m;

		int v[110][110], f[110][110];
		memset(f,0,sizeof f);
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= m; j++)
				cin >> v[i][j];

		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= m; j++)
				f[i][j] = max(f[i - 1][j], f[i][j - 1]) + v[i][j];
		cout << f[n][m] << endl;
	}
}

这里我们从1开始读入的，并且将f[][]初始状态置为0。这样当处理第一行或者第一列时，用到f[1][0]或者f[0][1]时，它们的值是0，不影响正常运算。

滚动数组

#include<iostream>
#include<cstring>

using namespace std;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);

	int T;
	cin >> T;
	while (T--)
	{
		int n, m;
		cin >> n >> m;

		int v[2][110], f[2][110];
		memset(v, 0, sizeof v);
		memset(f,0,sizeof f);
		
		for(int i=1;i<=n;i++)
		{
			for (int j = 1; j <= m; j++)
			{
				cin >> v[i & 1][j];
				// cout<<v[i&1][j]<<" ";
				f[i & 1][j] = max(f[i & 1][j - 1], f[(i - 1) & 1][j]) + v[i & 1][j];
				// cout<<f[i&1][j]<<" ";
			}
// 			cout<<endl;
	    }
		cout << f[n & 1][m] << endl;
	}
}

记忆化搜索

#include<iostream>
#include<cstring>

using namespace std;
const int N=110,INF=0x3f3f3f3f;
int n, m;
int p[N][N],f[N][N];

int dp(int x,int y)
{
    // 如果大于等于0，说明这个点已经被搜索过
    if(f[x][y]>=0)
        return f[x][y];
        
    // 处理边界情况，由于是求最大值，所以我们赋值为负无穷
    if (x < 1 || x > n || y < 1 || y > m) return f[x][y] = -INF; 
    
    // 如果是起点
    if(x==1 and y==1)
        return f[x][y]=p[x][y];
        
    // 普通情况
    f[x][y]=max(f[x][y],dp(x-1,y)+p[x][y]);
    f[x][y]=max(f[x][y],dp(x,y-1)+p[x][y]);
    return f[x][y];
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);

	int T;
	cin >> T;
	while (T--)
	{
		cin >> n >> m;
		
		// initial 全部置为-1，表示未被搜索
        memset(f, -1, sizeof f);
        
		for(int i=1;i<=n;i++)
		    for(int j=1;j<=m;j++)
		        cin>>p[i][j];
                
        dp(n,m);
        
        cout<<f[n][m]<<endl;
	}
	return 0;
}

写在最后

如果你觉得我写题解还不错的，请各位王子公主移步到我的其他题解看看
数据结构与算法部分（还在更新中）：
C++ STL总结 - 基于算法竞赛（强力推荐）
动态规划——01背包问题
动态规划——完全背包问题
动态规划——多重背包问题
动态规划——分组背包问题
最短路算法——Dijkstra（C++实现）
最短路算法———Bellman_Ford算法（C++实现）
最短路算法———SPFA算法（C++实现）
最小生成树算法———prim算法（C++实现）
最小生成树算法———Kruskal算法（C++实现）
染色法判断二分图（C++实现）
Linux部分（还在更新中）：
Linux学习之初识Linux
Linux学习之命令行基础操作