dp easy 题(简单题）

解题思路:

注意事项:

参考代码:

//方法dp 时间复杂度o(n*m) 空间复杂度o(n*m),1<=n<=m<=30,最大900次，时间戳戳有余，空间戳戳有余
#include<iostream>
#include<vector>
using namespace std;
int n, m;
int main()
{
	cin >> n >> m;
	//创建dp数组 dp[i][j] 表示从1， 1走到i,j的所有可能方案
	vector<vector<int> > dp(n + 1, vector<int>(m + 1, 0));
	//base case
	dp[1][1] = 1;
	for (int i = 2; i <= n; i++)
		dp[i][1] = dp[i - 1][1];
	for (int i = 2; i <= m; i++)
		dp[1][i] = dp[1][i - 1];
	//暴力枚举
	for (int i = 2; i <= n; i++)
	{
		for (int j = 2; j <= m; j++)
		{
			//当前点行列都为偶数直接跳过，否则更新点的数据
			if ((i & 1) == 0 && (j & 1) == 0)
				continue;
			dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
		}
	}
	cout << dp[n][m] << endl;
	return 0;
}