C++动态规划DP题

Question

DP题，马前卒，代码求指正
思路是用map记录障碍点（记为1），dp时若非1则dp[i][j]=dp[i-1][j]+dp[i][j-1]
原题洛谷：https://www.luogu.com.cn/problem/P1002

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#define INF 1e9
using namespace std;

int dx[]={-2,-1,1,2,-2,-1,1,2};
int dy[]={-1,-2,-2,-1,1,2,2,1};
bool map[22][22];
int dp[22][22];

int Bx,By,Hx,Hy;
//dp[i][j]=dp[i-1][j]+dp[i][j-1]
int main(){
    memset(map,0,sizeof(map));
    cin>>Bx>>By>>Hx>>Hy;
    map[Hx][Hy]=1;
    for(int i=0;i<8;i++){
        int x=Hx+dx[i];
        int y=Hx+dy[i];
        if(x<0||y<0||x>Bx||y>By)continue;
        map[x][y]=1;
    }
    dp[0][1]=1;
    for(int i=1;i<Bx;i++){
        for(int j=1;j<By;j++){
            if(map[i][j]==0)dp[i][j]=dp[i-1][j]+dp[i][j-1];
        }
    }
    cout<<dp[Bx-1][By-1];
    return 0;
} 

Answer 1

看了代码有以下几个问题：

1.在记录是否为障碍物的数组中，应该将其定义为bool类型而不是int类型，因为它只有两个取值，0和1。

2.在记录是否为障碍物的数组中，应该将x和y的计算分别赋值给x和y，而不是将y赋值给x，这是因为y是dy数组中的元素，而dx数组中的元素应该赋值给x。

3.在dp的过程中，应该从0开始循环到Bx和By，而不是从1开始循环到Bx-1和By-1，因为dp[0][0]表示的是起点，而dp[Bx-1][By-1]表示的是终点。

4.dp[i][j]应该只在map[i][j]等于0的情况下更新，因为map[i][j]等于1表示这个点是障碍物，无法通过。

这个是修改过后的代码，你可以参考一下

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#define INF 1e9
using namespace std;

int dx[] = {-2, -1, 1, 2, -2, -1, 1, 2};
int dy[] = {-1, -2, -2, -1, 1, 2, 2, 1};
bool map[22][22];
int dp[22][22];

int Bx, By, Hx, Hy;

int main() {
    memset(map, 0, sizeof(map));
    cin >> Bx >> By >> Hx >> Hy;
    map[Hx][Hy] = true;
    for(int i = 0; i < 8; i++) {
        int x = Hx + dx[i];
        int y = Hy + dy[i];
        if(x < 0 || y < 0 || x > Bx || y > By) continue;
        map[x][y] = true;
    }
    dp[0][0] = 1;
    for(int i = 0; i <= Bx; i++) {
        for(int j = 0; j <= By; j++) {
            if(!map[i][j]) {
                if(i == 0 && j == 0) continue;
                if(i == 0) dp[i][j] = dp[i][j-1];
                else if(j == 0) dp[i][j] = dp[i-1][j];
                else dp[i][j] = dp[i-1][j] + dp[i][j-1];
            }
        }
    }
    cout << dp[Bx][By] << endl;
    return 0;
}