[数据结构与算法]洛谷——T157532过河卒 动态规划入门题

解析
根据题意：
1.根据给出马的位置，求出所有的障碍点，并在标志数组中将值设为1。
2.根据题意给出公式：dp[i][j]=dp[i-1][j]+dp[i][j-1];
3.根据标志数组，将公式转为程序
注意：
1.因为马的走向肯定有-2，所以此题要防止越界
2.因为数据量大，最好将dp数组定义为long long int

AC代码

#include <iostream>
using namespace std;
#define long long ll
const int ROW=40;
const int COL=40;
int isA[ROW][COL];
ll DP[ROW][COL];
int isR[9]={0,-1,-1,1,1,2,-2,2,-2};
int isC[9]={0,2,-2,2,-2,-1,-1,1,1};
int main(){
	int isRowEnd,isColEnd,isRowL,isColL;
	//定义接收用户输入的变量
	
	cin>>isRowEnd>>isColEnd>>isRowL>>isColL;
	//测试用例的输入
	
	isRowEnd+=2;
	isColEnd+=2;
	isRowL+=2;
	isColL+=2;
	//防止在求障碍点时越界
	
	for(int i=0;i<9;i++){
		isA[isRowL+isR[i]][isColL+isC[i]]=1;
	}
	//标记所有的障碍点为1
	
	DP[1][2]=1;
	//初始化
	
	for(int i=2;i<=isRowEnd;i++){
		for(int j=2;j<=isColEnd;j++){
			if(isA[i][j]==0){
				DP[i][j]=DP[i-1][j]+DP[i][j-1];
			}
		}
	}
	//公式转代码，求DP数组
	
	cout<<DP[isRowEnd][isColEnd]<<endl;
	//输出结果
	
	return 0;
}