动态规划问题，请大家看一下

两台月球矿车从A点向B点移动探测，每台矿车每次可以向右或向下移动一步，移动到的位置对应的数据为可采集的矿石数量 假设每台矿车矿石装载量无限，请求出两台矿车都到达B点后采集到的矿石数量总和最大值，并将他们经过的路径输出 动态规划问题
算法思想 代码和伪代码 复杂度（空间和时间）

img

可以当作一辆车，第一辆车先走，采集过的置为0，然后第2辆车再走.这种贪心策略是错误的

img


如上图所示，通过观察可以发现，该图的最优值应该为（3+2）+（1+3）=9
但如果按照上述思路，第一台矿车采矿值应为3+3+0=6，之后把图中第二行第一列和第2行第2列的2个3全部清零，之后第二台矿车再走，能够采矿数最多只有2，这时得到的解为6+2=8，不是全局最优解

用两个状态数组

(这题还真不简单啊)
像这种这么难的题目，我们干脆直接写个DFS，思考正解太浪费时间，应该还能骗点分

毕竟试过了好几种二维数组可能的状态，比如f[i][j]表示从(1,1)走到(i,j)的最大值，都不行。
最终才发现这是个双线程dp，用到四维数组。
两个车车火星车一个一个走，相当于同时走，这个应该也可以理解吧（相当于巧算周长）
然后就能想到这样一个数组：
f[i][j][k][g]表示两个车车火星车分别从(1,1)走到(i,j)和(k,g)，能拿到的矿石最大值。
f[i][j][k][g]的依赖项是：f[i-1][j][k][g-1],f[i-1][j][k-1][g],f[i][j-1][k][g-1],f[i][j-1][k-1][g]
操作：取最大值
注意由于是四维数组，容易爆空间，最好设置成f[129][129][129][129]比较安全。
代码：

#include<bits/stdc++.h>
using namespace std;
const int N=129;
int n,m,a[N][N],f[N][N][N][N];
int main() {
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            cin>>a[i][j];
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            for(int k=1;k<=n;k++)
                for(int g=1;g<=n;g++){
                    //此时，第一种走法走了i+j步，第二种k+g步 
                    int tem=max(f[i-1][j][k][g-1],f[i-1][j][k-1][g]); 
                    tem=max(tem,f[i][j-1][k][g-1]);
                    tem=max(tem,f[i][j-1][k-1][g]);
                    if(i==k&&j==g)f[i][j][k][g]=a[i][j]+tem;//同一个位置，不能加两次 
                    else f[i][j][k][g]=a[i][j]+a[k][g]+tem;//不同的位置，那就都所有的拿走矿石 
                }
    cout<<f[n][n][n][n];
    return 0;
}

设地图是M

  • 定义一个二维数组A_k存放在第k行的时候小车A位于j1,小车B位于j2时两个车采的总质量
  • 每次更新该数组A_{k+1}[j1][j2]=max([
    A_{k}[j1][j2]+M[k+1][j1]+M[k+1][j1],
    A_{k+1}[j1-1][j2]+M[k+1][j1],
    A_{k+1}[j1][j2-1]+M[k+1][j2]
    ])

把所有能走的路径都走一遍，然后找出最大数量就行了。

这得多维数组才行啊