P1002 过河卒

· · 题解

由于此题的空间还可优化，于是才有了这篇题解。

动态规划(递推?)

设DP_{i,j}为卒从起点走到(i,j)点所有可行的路径总数，所以DP_{0,0}=1，我们要求的就是DP_{n_{x},n_{y}}。

通过卒行走的规则可以得出状态转移方程(在下面)，马需要判断一下即可。(标记数组只是其中一种方法)

要注意数组越界的坑；答案要用long\ long，在此题的数据范围中，最大的答案大到137846521561，这个数字用int已经存不下了。

状态转移方程DP_{i,j}=DP_{i-1,j}+DP_{i,j-1}

#include<cstdio>
const int Const[2][9]={{0,-2,-1,1,2,2,1,-1,-2},{0,1,2,2,1,-1,-2,-2,-1}};
long long DP[21][21]={1};
bool mark[21][21];
int main() {
    int nx,ny,hx,hy;
    scanf("%d%d%d%d",&nx,&ny,&hx,&hy);
    for(int i=0;i<9;++i)
        if(hx+Const[0][i]>=0&&hx+Const[0][i]<=nx&&hy+Const[1][i]>=0&&hy+Const[1][i]<=ny)
            mark[hx+Const[0][i]][hy+Const[1][i]]=1;
    for(int i=0;i<=nx;++i)
        for(int j=0;j<=ny;++j) {
            if(i)
                DP[i][j]+=DP[i-1][j];
            if(j)
                DP[i][j]+=DP[i][j-1];
            DP[i][j]*=!mark[i][j];
        }
    printf("%lld",DP[nx][ny]);
    return 0;
}

空间复杂度O(n_xn_y)

时间复杂度O(n_xn_y)

动态规划(递推?)+滚动数组

![](https://cdn.luogu.com.cn/upload/pic/12450.png) ![](https://cdn.luogu.com.cn/upload/pic/12453.png) 因为$DP_{i,j}$~$DP_{i,n_{y}}$还没有运算，所以可以让$DP_{i-1,j}$~$DP_{i-1,n_{y}}$向下平移代替$DP_{i,j}$~$DP_{i,n_{y}}$，可以使用滚动数组实现。 **状态转移方程**$DP_{i}=DP_{i}+DP_{i-1} 
#include<cstdio>
const int Const[2][9]={{0,-2,-1,1,2,2,1,-1,-2},{0,1,2,2,1,-1,-2,-2,-1}};
long long DP[21]={1};
bool mark[21][21];
int main() {
    int nx,ny,hx,hy;
    scanf("%d%d%d%d",&nx,&ny,&hx,&hy);
    for(int i=0;i<9;++i)
        if(hx+Const[0][i]>=0&&hx+Const[0][i]<=nx&&hy+Const[1][i]>=0&&hy+Const[1][i]<=ny)
            mark[hx+Const[0][i]][hy+Const[1][i]]=1;
    for(int i=0,j;i<=nx;++i)
        for(DP[0]*=!mark[i][0],j=1;j<=ny;++j)
            (DP[j]+=DP[j-1])*=!mark[i][j];
    printf("%lld",DP[ny]);
    return 0;
}

空间复杂度O(n_y)

时间复杂度O(n_xn_y)

未解决的问题

1.这种做法到底是动态规划还是递推，还是说简单动态规划=递推？