从最后一步往前想,就可以得到了,应该算是对DP的初步理解
#include <iostream>
using namespace std;
const int N = 110;
int n,r,c;//n几亩花生田,r行数,c列数
int a[N][N],d[N][N];//花生田每个位置有多少花生
int main()
{
cin >> n;
for(int i = 0;i < n;i ++)
{
cin >> r >> c;
for(int j = 1;j <= r;j ++)
for(int k = 1;k <= c;k ++)
cin >> a[j][k];
for(int j = 1;j <= r;j ++)
for(int k = 1;k <= c;k ++)
d[j][k] = max(a[j][k] + d[j - 1][k],a[j][k] + d[j][k - 1]);
cout << d[r][c] << endl;
}
}
DP
#include <iostream>
using namespace std;
const int N = 110;
int n,r,c;//n几亩花生田,r行数,c列数
int d[N][N];//花生田每个位置有多少花生
int main()
{
cin >> n;
for(int i = 0;i < n;i ++)
{
cin >> r >> c;
for(int j = 1;j <= r;j ++)
for(int k = 1;k <= c;k ++)
cin >> d[j][k];
for(int j = 1;j <= r;j ++)
for(int k = 1;k <= c;k ++)
d[j][k] = max(d[j - 1][k],d[j][k - 1]) + d[j][k];
cout << d[r][c] << endl;
}
}
DP优化(其实么看出哪里优化了 -QAQ-),主要是与1进行&运算时,先换成2进制,看个位
#include <iostream>
#include <cstring>
using namespace std;
const int N = 110;
int n,m;
int a[N][N];
int f[2][N];
int main ()
{
int T;
cin >> T;
while (T--)
{
memset (f,0,sizeof (f));
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 & 1][j] = max (f[(i - 1) & 1][j],f[i & 1][j - 1]) + a[i][j];
//共两位,如果二进制个位是1则,该位的结果存在第二行,否则存在第一行
}
cout << f[n & 1][m] << endl;
}
return 0;
}