代码编织梦想

面经|百度春招2023.3.07第三道算法题:走格子(要求走奇数步)

Problem Description

现在有一个nxm矩阵,小红在(1,1),终点(n,m)。(1,1)在左上,(n,m)在右下。每次可以往下或者往右走,步数需要是奇数。小红想知道她有多少种方案到终点,你能帮她算一下吗?

input

有T组测试用例,第一行输入一个正整数,表示用例组数。 接下来T行,每行两个正整数n和m ,表示矩阵的大小。1≤T,n,m≤2000

Sample Input

1
2 4

Sample Output

6

说明

一共有以下方案:
(1, 1) > (1,2) > (1,3) > (1,4) > (2,4)
(1, 1) > (1,2) > (1,3) > (2,3) > (2,4)
(1, 1) > (1,2) > (2,2) > (2,3) > (2,4)
(1, 1) > (2,1) > (2,2) > (2,3) > (2,4)
(1,1) > (1,4) > (2,4)
(1, 1) > (2, 1) > (2,4)

一、题目类型、难度

  • 类型:动态规划
  • 难度:简单题

二、总体思路:

  • 常规走格子型题目:从左上角走到右下角,每次只能走一步,问有多少种走法。
    • 本题加多一个条件:每次走的步数不一定为1,而是可以走任意奇数步
  • 可以使用动态规划解决。
    • dp数组形状及含义:建立一个n行,m列二维数组dp[n][m]。其中dp[i][j]表示走到坐标(i+1, j+1)的方法数。因此要求得走到右下角的方法数,只要求dp[n-1][m-1]
    • 边界条件:此题初始条件只有一个,就是走到左上角(1,1)的方法数是1。因此设置dp[0][0]=1。
    • dp数组更新顺序及条件:因为每次只能往右走或往下走奇数步,反过来想,如果要走到第(i,j)格,则只能从上方或左方走来。只要把所在行左方距离本格奇数步格子的方法数和所在列上方距离本格奇数步格子的方法数相加即可得到走到本格的方法数。因此可以使用逐行,从左往右计算。也可以使用逐列,从上往下计算。本方法使用第一种计算顺序。
      • 举个例子。比如现在我要计算走到(4,3)格要走多少步,那我要知道从哪些格子可以走到(4,3)。首先看同行的:(4,0)距离(4,3) 3步;(4,1)距离(4,3) 2步;(4,2)距离(4,3) 1步;因此可以从(4,0)和(4,3)走到(4,3)。同理,同列中有(1,3),(3,3)可以用奇数步走到(4,3)。因此(4,0),(4,3),(1,3),(3,3)都可以走到(4,3)。走到(4,3)的方法数就等于走到(4,0),(4,3),(1,3),(3,3)的方法数之和
    • 转移方程:
      • d p [ i ] [ j ] = ∑ k 1 = 0 j − 1 d p [ i ] [ k 1 ] + ∑ k 2 = 0 i − 1 d p [ k 2 ] [ j ] dp[i][j] = \sum^{j-1}_{k1=0}{dp[i][k1]}+\sum^{i-1}_{k2=0}{dp[k2][j]} dp[i][j]=k1=0j1dp[i][k1]+k2=0i1dp[k2][j]
        • ( j − k 1 ) m o d 2 = 1 (j-k1)mod2=1 (jk1)mod2=1
        • ( i − k 2 ) m o d 2 = 1 (i-k2)mod2=1 (ik2)mod2=1

代码

#include <iostream>
#include <algorithm>
using namespace std;
int cal(int n, int m){
	int dp[n][m] = {0};
	//init
	dp[0][0] = 1;
	// DP
	for (int i = 0; i < n; i++){
		for (int j = 0; j < m; j++){
			if (i == 0 && j == 0) continue;
			dp[i][j] = 0;
			// 计算行 
			for (int k = 0; k < j; k++){
				if ((j-k)%2 == 1){
					dp[i][j] += dp[i][k];
				}
			}
			// 计算列 
			for (int k = 0; k < i; k++){
				if ((i-k)%2 == 1){
					dp[i][j] += dp[k][j];
				}
			}
		}
	}
	return dp[n-1][m-1];
}

int main(){
	int T, n, m;
	cin >> T;
	for (int i = 0; i < T; i++){
		cin >> n >> m;
		cout << cal(n, m) << "\n";
	}
	return 0;
}

三、增加难度

  • 题目中只需要输出方法数。那如果题目要我们输出全部的路径,这时候应该怎么做?
  • 待更新!
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/weixin_40735291/article/details/129630737