求优化dp

学术版

穼柗° @ 2024-11-28 21:38:21

x=y$ 时，$dp_{x,y}=1\\ x>y$ 时，$dp_{x,y}=dp_{x-2,y}+dp_{x-1,y-1}

怎么样把它优化到 O(1) 或 O(\log{x})？

by 穼柗° @ 2024-11-28 21:41:50

哦对了少了一句：\

x=y+1$ 时，$dp_{x,y}=2

by z_z_b_ @ 2024-11-28 21:42:36

@穼柗° 嘶……有没有x,y的范围或者直接是具体题目？

by 穼柗° @ 2024-11-28 21:44:25

@z_zb y\leq x \leq 10^5。

by UMS2 @ 2024-11-28 21:48:22

@穼柗° 组合数学

by 穼柗° @ 2024-11-28 21:49:37

@UMS2 好像还真是组合数学哦

by 穼柗° @ 2024-11-28 21:50:48

@z_zb 具体题目\ \ 这里的 n,l 对应我说的 x,y

by 穼柗° @ 2024-11-28 21:51:15

所以怎么做qwq

by AzusidNya @ 2024-11-28 21:51:19

@穼柗°

考虑这个 dp 的本质。

把 (x, y) 当作坐标系上的点，那么一次操作相当于向右上角走一格或者向右走两格。实际上求的是从 y = x 直线上走到给定点的方案数之和吧。

注意到向上走一定是向右上角走，所以应该可以将坐标系直接挪一下，并且将 x 坐标除以 2。然后就成了从 y 轴上任意点走到一个给定点的方案数。

组合数即可。

by z_z_b_ @ 2024-11-28 21:52:19

@穼柗° 生成函数秒了/lh

by 穼柗° @ 2024-11-28 21:53:11

@AzusidNya 蟹蟹٩('ω')و

| 下一页