生物

信息竞赛中的一些算法、生物信息学相关算法：动态规划

应 这个可以有 的建议，这个帖子放在生物区。

这是一个关于信息竞赛（生物信息学）的帖子。

$A\to B$ 表示把 $A$ 的值设为 $B$。

$a[i]$ 表示数组 $a$ 的第 $i$ 项。

$i$ 除非特殊说明，不指虚数单位。

某些词语可能使用不规范，请大家指出。

$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$

……

……

……

（前面情节忘记了）

于是学编程的小女孩再也看不到这道动态规划题了。

有人说：“她只是想写一个状态转移方程。”

（选自《学编程的小女孩》，作者未知）

－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－

P1002 过河卒

我相信很多人做完 P1000 超级玛丽游戏和 P1001 A + B Problem 后肯定想做 P1002，但是发现不会做。因为我就是这样的人。

题目描述（简化版）：

$n\times m$ 的棋盘上，有一个卒和一个马。卒需要从 $1,1$ 的位置到 $n,m$ 的位置，它一次只能向右或向下移动一格。

同时在 $a,b$ 的位置有一匹马。卒不能走到会被马吃掉的位置或马的位置，马不会移动。

求路线数量。

设 $dp[i][j]$ 为到 $i,j$ 的路线数，可以得到 $dp[i][j]=dp[i-1][j]=dp[i][j-1]$。

但是我们还需要处理特殊情况，如 $i,j$ 的位置被马控制，则 $dp[i][j]=0$。

看到这里，你既然看到了表达式，肯定非常想用递归计算。但递归太慢了。

动态规划就是一种替代递归的算法。绝大多数可以用动规解决的问题也可以用递归解决。

我们发现 $dp[1][2]$ 被求了很多次，所以我们是否可以定义变量 $dp12$ 来存储它的值呢？

既然定义了 $dp12$，为什么不定义 $dp13$、$dp14$？

为什么不用数组来表达它呢？

动规就是定义一个数组，使用已知量求出未知量。

例如 $n=m=5,i=j=2$，我们可以得到：

$dp[1][1]=1$

$dp[1][2]=1$

$dp[1][3]=1$

$dp[1][4]=0$

$dp[1][5]=1$

$dp[2][1]=1$

$dp[2][2]=0$

$dp[2][3]=dp[1][3]+dp[2][2]=1$

$dp[2][4]=dp[1][4]+dp[2][3]=1$

$dp[2][5]=dp[1][5]+dp[2][4]=2$

$dp[3][1]=1$

$dp[3][2]=dp[2][2]+dp[3][1]=1$

$dp[3][3]=dp[2][3]+dp[3][2]=2$

$dp[3][4]=0$

$dp[3][5]=dp[2][5]+dp[3][4]=2$

$dp[4][1]=0$

$dp[4][2]=dp[3][2]+dp[4][1]=1$

$dp[4][3]=0$

$dp[4][4]=dp[3][4]+dp[4][3]=0$

$dp[4][5]=dp[3][5]+dp[4][4]=2$

$dp[5][1]=1$

$dp[5][2]=dp[4][2]+dp[5][1]=2$

$dp[5][3]=dp[4][3]+dp[5][2]=2$

$dp[5][4]=dp[4][4]+dp[5][3]=2$

$dp[5][5]=dp[4][5]+dp[5][4]=4$

所以答案就是 $4$。