NOIP2018提高组金牌训练营——动态规划专题
https://www.51nod.com/Live/LiveDescription.html#!#liveId=19
多重背包
二进制优化转化成01背包就好了
一只猪走进了一个森林。很凑巧的是，这个森林的形状是长方形的，有n行，m列组成。我们把这个长方形的行从上到下标记为1到n，列从左到右标记为1到m。处于第r行第c列的格子用(r,c)表示。
刚开始的时候猪站在(1,1),他的目标是走到(n,m)。由于猪回家心切，他在(r,c)的时候，只会往(r+1,c)或(r,c+1)走。他不能走出这个森林。
这只猪所在的森林是一个非同寻常的森林。有一些格子看起来非常相似，而有一些相差非常巨大。猪在行走的过程中喜欢拍下他经过的每一个格子的照片。一条路径被认为是漂亮的当且仅当拍下来的照片序列顺着看和反着看是一样的。也就是说，猪经过的路径要构成一个回文。
数一数从(1,1)到(n,m)有多少条漂亮路径。答案可能非常巨大，请输出对 $10^9+7$ 取余后的结果。
样例解释：有三种可能
单组测试数据。 第一行有两个整数 n,m (1≤n,m≤500)，表示森林的长和宽。 接下来有n行，每行有m个小写字母，表示每一个格子的类型。同一种类型用同一个字母表示，不同的类型用不同的字母表示。
输出答案占一行。
3 4 aaab baaa abba
3
注意到500分数据范围，考虑n三方的算法
发现回文非常难判断，可能要记录整个路径，不现实
所以从两端开始搜
f[x1][y1][x2][y2]表示从（1， 1）到（x1,y1），从(n, m)走到(x2, y2)
的方案数。这样就很好转移了，有四个方程，分别对应从（1， 1）往下还是往右
(n, m)往上还是往左
但是发现这样会炸空间，炸时间
那么显然有x1 + y1 = x2 + y2
那么f[x1][y1][x2]可以省去一维
但这样会炸空间
怎么办？
可以这样设计f[step][x1][x2]， step = x1 + y1
有什么区别？
这样的话step的这一维只和step-1有关
所以可以用滚动数组优化掉一维的空间。
那么这道题就完美的解决了。
代码略……
原文：https://www.cnblogs.com/sugewud/p/9899989.html