两台月球矿车从A点向B点移动探测,每台矿车每次可以向右或向下移动一步,移动到的位置对应的数据为可采集的矿石数量 假设每台矿车矿石装载量无限,请求出两台矿车都到达B点后采集到的矿石数量总和最大值,并将他们经过的路径输出 动态规划问题
算法思想 代码和伪代码 复杂度(空间和时间)
可以当作一辆车,第一辆车先走,采集过的置为0,然后第2辆车再走.这种贪心策略是错误的
如上图所示,通过观察可以发现,该图的最优值应该为(3+2)+(1+3)=9
但如果按照上述思路,第一台矿车采矿值应为3+3+0=6,之后把图中第二行第一列和第2行第2列的2个3全部清零,之后第二台矿车再走,能够采矿数最多只有2,这时得到的解为6+2=8,不是全局最优解