算法与数据结构---过河卒-递推（动态规划）写法常见易错点

一、总结

一句话总结：

对于有负数情况的递推（动态规划）问题，比如过河卒，f[i][j]=f[i-1][j]+f[i][j-1]，采用的策略一般都是加数让它变成正数

1、直接填表更新状态会有问题，那些被马控制的点不能被更新状态，始终要是0？

|||-begin

//如果直接这样写，那么马控制点点也会被更新，
//马控制的点始终是0，不能被更新
for(int i=1;i<=bx;i++){
    for(int j=1;j<=by;j++){
        f[i][j]=f[i-1][j]+f[i][j-1];
    }
}

|||-end

而如上写法被马控制的点会被更新

//如果直接这样写，那么马控制点点也会被更新，
//马控制的点始终是0，不能被更新
for(int i=1;i<=bx;i++){
    for(int j=1;j<=by;j++){
        if(!control[i][j])
        f[i][j]=f[i-1][j]+f[i][j-1];
    }
}

2、从0开始遍历的时候，要保证f[0][0]这个初始点不要被覆盖？

所以需要对f[0][0]进行特判

//初始化f数组
f[0][0]=1;
//将马控制得到的位置初始化到f数组
for(int i=0;i<=8;i++){
    //马的位置没出界
    int now_x=mx+hx[i];
    int now_y=my+hy[i];
    if(now_x>=0&&now_x<=bx&&now_y>=0&&now_y<=by){ 
        control[now_x][now_y]=1;
    } 
}
//如果直接这样写，那么马控制点点也会被更新，
//马控制的点始终是0，不能被更新
for(int i=0;i<=bx;i++){
    for(int j=0;j<=by;j++){
        if(i||j)
        if(!control[i][j]){
            //f[i][j]=f[i-1][j]+f[i][j-1];
            if(i>=1&&j>=1)
            f[i][j]=f[i-1][j]+f[i][j-1];
            else if(i>=1)
            f[i][j]=f[i-1][j];
            else if(j>=1) f[i][j]=f[i][j-1];
            else f[i][j]=0;
        } 
    }
}

二、过河卒-递推（动态规划）写法常见易错点

博客对应课程的视频位置：

1、题目描述

题目位置

P1002 过河卒 - 洛谷
https://www.luogu.com.cn/problem/P1002

2、代码

 1 /*
 2 
 3 递推表达式（状态转移方程）：
 4 f[i][j]=f[i-1][j]+f[i][j-1]
 5 
 6 初始状态：
 7 马控制的点为0
 8 f[0][0]=1
 9 
10 
11 */
12 #include <iostream>
13 #include <cstring>
14 using namespace std;
15 int hx[9]={0,-2,-1,1,2,2,1,-1,-2};
16 int hy[9]={0,1,2,2,1,-1,-2,-2,-1};
17 long long f[25][25]={0};
18 bool control[25][25]={0};
19 int main(){
20     int bx,by,mx,my;
21     cin>>bx>>by>>mx>>my;
22     //bx+=1;by+=1;mx+=1;my+=1;
23 
24     //初始化f数组
25     f[0][0]=1;
26     //将马控制得到的位置初始化到f数组
27     for(int i=0;i<=8;i++){
28         //马的位置没出界
29         int now_x=mx+hx[i];
30         int now_y=my+hy[i];
31         if(now_x>=0&&now_x<=bx&&now_y>=0&&now_y<=by){ 
32             control[now_x][now_y]=1;
33         } 
34     }
35     //如果直接这样写，那么马控制点点也会被更新，
36     //马控制的点始终是0，不能被更新
37     for(int i=0;i<=bx;i++){
38         for(int j=0;j<=by;j++){
39             if(i||j)
40             if(!control[i][j]){
41                 //f[i][j]=f[i-1][j]+f[i][j-1];
42                 if(i>=1&&j>=1)
43                 f[i][j]=f[i-1][j]+f[i][j-1];
44                 else if(i>=1)
45                 f[i][j]=f[i-1][j];
46                 else if(j>=1) f[i][j]=f[i][j-1];
47                 else f[i][j]=0;
48             } 
49         }
50     }
51     
52     cout<<f[bx][by]<<endl;
53     return 0;
54 }