女娲补天之数字三角形
数字三角形的题面还是比较好理解的,通常是一个矩形的图或者是三角形的图,要从左上角走到右下角,且每次只准向下或向右移动,问经过的位置上之和的最大/小值是多少
对普通的数字三角形模型,只需要一个二维的数组f[i, j]
状态含义是从(1, 1)
到(i, j)
点的所有方案的集合。
状态属性:Max(Min)
状态计算:由于每次只能从上或者从右转移过来
$(i, j)$从$(i-1, j)$即上方过来
$(i, j)$从$(i, j-1)$即左方过来
二者再取一个较大值即可
注意普通数字三角形需要注意两个点
第一个是:注意在最左边一列的位置是只能从上方转移,最上面一行的位置只能从左边转移过来
if i == 1:
f[i][j] = f[i][j - 1] + w[i][j]
elif j == 1:
f[i][j] = f[i -1][j] + w[i][j]
第二个是:DP问题需要初始化,一般普通数字三角形只需要f[1][1] = w[1][1]
以上是针对走一次的情况,那么对于走两次的情况(前一次经过的点上的数被取走后,后面再经过后不会计算)
这里主要学习了一次性走两个的方法。
因为二者有可能走同一个位置,如何判断两个点是否重合就是大问题,对于第一个点i1,j1
和第二个点i2, j2
,如果
i1 + j1 = i2 + j2
的话,说明二者重合了,这个点的值只要加一次就行。
那么可以让两个人同时出发,每次各走一步,多一维记录走过的总步数,这样既能很好的表示二者重合的情况,也不至于用四维去进行状态转移f[i1][j1][i2][j2]
,只需要f[k][i1][i2]
,那么j1 = k - i1
,j2 = k - i2
,i1 = i2
表示重合。
在普通数字三角形问题中,最后一步的转移有两种情况,从上面或者从左边转移过来,这里走两次的情况则是$2$ X $2$ = $4$种情况。
两个人同时走,分别为$A$和$B$
$0$:代表要走下边一个格子
$1$:代表要走右边一个格子
集合划分为四类:00,01,10,11
图片参考于:郡呈
刷题列表:
AcWing 898. 数字三角形
原始模板题,但需要注意建模的方式。
AcWing 1015. 摘花生
一次遍历矩阵模板题。
AcWing 1018. 最低通行费
一次遍历矩阵模板题,时间的限制使其不能走回头路,只能向下或者向右移动。
AcWing 1027. 方格取数
二次遍历矩阵模板题。
AcWing 275. 传纸条
二次遍历矩阵模板题。