SP26719题解

考虑动态规划。

思路

设 \(dp_{i,j}\) 为 \((1,1)\) 到 \((i,j)\) 的方案数，而如果要到这个点，肯定是从左边和上边来。

所以递推公式为：\(dp_{i,j}= dp_{i,j-1} + dp_{i-1,j}\)。

预处理：将横或纵坐标为 1 的点赋值为 1，因为到达这些点的只有一种方法。

注意：

• 每次需要清零数组。

AC CODE

#include<iostream>
#include<algorithm>
#include<string>
#include<cstring>
using namespace std;
int T;
int dp[10][10];
signed main(){
	cin>>T;
	while(T--){
		int x,y;
		cin>>x>>y;
		memset(dp,0,sizeof dp);//预处理 
		dp[1][1]=1;
		for(int i=1;i<=max(x,y);i++)dp[i][1]=dp[1][i]=1;
		//动态规划 
		for(int i=2;i<=x;i++){
			for(int j=2;j<=y;j++){
				dp[i][j]=dp[i-1][j]+dp[i][j-1];
			}
		}
		cout<<dp[x][y]<<endl;
	}
	return 0;
}