DP入门_关于方格问题_P1002/P1004

D(ynamic) P(rogramming)

https://zhuanlan.zhihu.com/p/365698607

可以参考

然后针对方格问题,如 P1002

先拿斩马刀

给他马一刀

简单地,我们得到以下事实:

通往任意一点的路线数量等于相邻两点数量的和.

(只能由这两点到这一点,既然走到这两点的路线数是一定的,那走到这个点自然不会变,只是在原有路线后加了一个点而已,类似于1+1+....)

也就是

也就是图中表示的两个箭头:上面和左边加起来就等于这一格的数字

有点像杨辉三角

其他几个条件也很简单:

边界:x或y中有一个为0,也就是坐标边界,那必然为1(图中给出),因为除了直线无路可走

最优子结构:就是左边和上面的数字和

重叠子问题:

如果直接设定边界f(xy = 0) = 1,则会发生和例题中递归方法一样的后果:
f(2,1)->f(1,1)+f(2,0)

f(1,2)->f(1,1)+f(0,2)

f(1,2) & f(2,1):HXD咱们一起走

所有数字将从1开始累加,显然,时间复杂度很高

解决办法也很简单,从已知入手,一点点叠加,如图所示.从左上角开始而不是从右下角反推

注意在这么推的时候,马所控制的点无条件改为0即可,因为不可到达

我知道你很急,但你先别急  (一会有你急的)

常规开局,如果用万能库<bits/std++>也行,快读快写什么的当然更好,这里当个原始人(简洁!(bushi))

声明变量和函数

注意:只有全局变量会被初始化为默认值0,局部变量将会是随机数,是直接接手的原来的内存而没有调整.这一点需要有所注意

输入数据,没啥好说的,等效于cin>>Bx>>By....这里为了对称美观

+1是为了直接取Bx,By方便,开long long 是为了防止数据量过大爆掉

Homo特有的无意义初始化

((i == Mx-2 || i == Mx+2) && (j == My-1 || j == My+1)) || ((i == Mx-1 || i == Mx+1) && (j == My-2 || j == My+2)) || (i == Mx && j == My)

这坨很长,但很简单:判断是不是马所控制的九个点,这里只是傻乎乎得全列出来了而已

init相关的几句是为了:如果初始化的路上有一个点是0,那后面的点必然全是0如

11111110(此时init为了)00000

一模一样的y方向,不用看了,x改y就能跑

重头戏来了,公式熟悉吗,就是那个状态转移方程!(if内是那一坨判断🐎的玩意)

输出,结束 (原代码里还有一坨是遍历这个二维数组的,对解题没啥用)

对于一个15*15且没有阻碍的方格,按照规定,有 155117520 种走法,直逼16E,再扩大一点int就会爆炸了.

P1004?累了,待会再写....