求助帖 dp做法 3 4一直wa
查看原帖
求助帖 dp做法 3 4一直wa
951263
Theviro楼主2023/2/25 18:21

考虑了边界条件 采用自底向上的dp 请问这个代码怎么改?

#include<stdio.h>
#include<stdlib.h>

#define MAX 25
#define INF -1
long long dp[MAX][MAX];

void DP(int n,int m)
{
	int i,j;
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=m;j++)
		{
			if(dp[i][j]==0) continue;
			else dp[i][j]=dp[i-1][j]+dp[i][j-1];
		}
	}
	printf("%lld\n",dp[n][m]);
}


int main()
{
	int n,m;
	int x,y;
	scanf("%d %d",&n,&m);
	scanf("%d %d",&x,&y);
	int i,j;
	//初始化表格所有位置都为无穷大(未知即为无穷大)
	for(i=0;i<=n;i++) for(j=0;j<=m;j++) dp[i][j]=INF; 
	//找到马的落点并设为0
	for(i=-2;i<=2;i++)
	{
		if(i==0)
		{
			dp[x][y]=0;
			continue;
		}
		j=2/i;
		if(x+i<0||x+i>n) continue;
		if(y+j<0||y+j>m) continue;
		if(y-j<0||y-j>m) continue; 
		dp[x+i][y+j]=0;
		dp[x+i][y-j]=0;
	}
	//注意考虑一个问题:就是如果马的一个步子落在了边界上的某个点,那么这个点后边的所有值都得改成0 
	int val;
	//初始化二维数组的边界都为1 
	dp[0][0]=1;
	val=1;
	for(i=0;i<=n;i++)
	{
		if(dp[i][0]==0) val=0;
		dp[i][0]=val;
	}
	val=1;
	for(i=0;i<=m;i++) 
	{
		if(dp[0][i]==0) val=0;
		dp[0][i]=val;
	}
	//测试 
//	for(i=0;i<=n;i++) 
//	{
//		for(j=0;j<=m;j++) printf("%d\t",dp[i][j]);
//		printf("\n\n");
//	}
	//动态规划
	DP(n,m); 
	return 0;
}
2023/2/25 18:21
加载中...