方格取数问题

标签

动态规划/数字三角形

字数

480 字

阅读时间

2 分钟

---

题目解析源地址：这里

题目

思路

提示（错误思路）

正确思路

1. 已知需要走两条路线，且不能重复，因为方格中的数字只能取一次，则我们假设两条路线同时从方格左上角出发，那么如果两条路径重合，则必定出现 $i_1+j_1==i_2+j_2$
2. 可以考虑使用四维数组 $f[i_1][j_1][i_2][j_2]$ 来维护两条路径取值和的最大值，但这样设置数组会导致空间复杂度到达 $O(n^4)$，故可以根据第一点中提到的条件来降维，令 $k==i_1+j_1==i_2+j_2$，故可以用三维数组 $f[k][i_1][i_2]$ 来维护两条路径取值和的最大值
3. 确定好数组后，需要考虑k相同时，两条路径到达目标点的方式，可分为以下四种可能性，即：A 从方格左上角出发，当k确定时，到达目的点 $(i_1,j_1)$ 可能存在从左边过来，或从上边下俩两种可能性，即：$(1,1)\to (i_1-1,j_1)\to (i_1,j_1)$ 或 $(1,1)\to (i_1,j_1-1)\to (i_1,j_1)$ ，同理，另一条路径到达 $(i_2,j_2)$ 也有两种可能，那么将这两种路径的可能性组合起来，则一共有4种组合，故 $f[k][i_1][i_2]$ 的状态表达式为：
   • 令 $t=w[i_1][j_1]$，如果 $i_1==i_2$，则说明这两条路线同一时刻到达的这个点相同，则只加一次(因为只能取一次)，否则 $t+=w[i_2][j_2]$
   1. $f[k][i_1][i_2]=f[k-1][i_1][i_2]+t$
   2. $f[k][i_1][i_2]=f[k-1][i_1-1][i_2]+t$
   3. $f[k][i_1][i_2]=f[k-1][i_1][i_2-1]+t$
   4. $f[k][i_1][i_2]=f[k-1][i_1-1][i_2-1]+t$

• 最后一定要注意边界判断！！！因为 $j_1=k-i_1$，所以要判断 $j_1$ 的取值是否在 $[0,n]$ 的区间内，$j_2$的判断也同理

贡献者

freeway348

文件历史

最后编辑于 11 天前查看完整历史

134d9-Dp