递归上手
先分析成递归的形式,再由递归修改成循环形式的动态规划
只有两个方向,故新的点一定是由
i-1,j
或者i,j-1
处得到的
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
const int n = 110;
int N, M;
vector<vector<int>> v(n, vector<int>(n));
int dp[n][n];
int dfs(int x, int y)
{
// 越界
if (x >= N || y >= M)
return 0;
// 结尾
if (x == N - 1 && y == M - 1)
return dp[x][y] = v[x][y];
// DP
if (dp[x][y] != 0)
return dp[x][y];
// 选最大
return dp[x][y] = max(dfs(x + 1, y), dfs(x, y + 1)) + v[x][y];
}
int main()
{
int T;
cin >> T;
while (T--)
{
memset(dp, 0, sizeof(dp));
cin >> N >> M;
for (int i = 0; i < N; i++)
for (int j = 0; j < M; j++)
{
cin >> v[i][j];
}
cout << dfs(0, 0) << endl;
}
return 0;
}
一级修改
像刚才说的一样,直接修改就行
注:递归的循环和这个写的顺序不一样
#include<iostream>
using namespace std;
const int n = 110;
int f[n][n];
int a[n][n];
int main()
{
int T;
cin >> T;
while(T--)
{
int N, M;
cin >> N >> M;
for(int i = 1;i <= N;i++)
for(int j = 1;j <= M;j++)
cin>> a[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]) + a[i][j];
cout << f[N][M] << endl;
}
return 0;
}
二级修改
我们尝试直接删去第一维
出现答案错误,分析一下得出:f
需要清零,由于递推式是:f[j] = max(f[j], f[j - 1]) + a[i][j];
用到了上一层的f[j]
,所以~
#include <iostream>
#include <cstring>
using namespace std;
const int n = 110;
int f[n];
int a[n][n];
int main()
{
int T;
cin >> T;
while(T--)
{
int N, M;
cin >> N >> M;
for(int i = 1;i <= N;i++)
for(int j = 1;j <= M;j++)
cin>> a[i][j];
memset(f, 0, sizeof(f));
for(int i = 1;i <= N;i ++)
for(int j = 1; j<= M;j++)
f[j] = max(f[j], f[j - 1]) + a[i][j];
// for(int i = 1;i <= N;i++)
// cout << f[i] <<' ';
cout << f[M] << endl;
}
return 0;
}