Lattice paths

Starting in the top left corner of a 2×2 grid, and only being able to move to the right and down, there are exactly 6 routes to the bottom right corner.

image-20210311194132170

How many such routes are there through a 20×20 grid?

1.递推法

递推法：dp[x][y] = dp[x - 1][y] + dp[x][y - 1]

  1. 网格中到达任意一点的路径方案数 = 正上方方案数 + 正下方方案数:dp[x][y] = dp[x - 1][y] + dp[x][y - 1]
  2. 递推边界为左上角点（1，1）,结果为右下角点坐标（4，4）

image-20210417200559554

  • 定义循环(i, j)需要从点(1, 1)点开始

  • 这样外边界有一圈保护0，不需要判断边界、不用考虑数组越界问题（数字0不会影响答案）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<iostream>
using namespace std;

long long ans[25][25];

int main(){
    for(int i = 1; i <= 21; ++i){
        for(int j = 1; j <= 21; ++j){
            //初始化左上角点的值为(1, 1)
            if(i == 1 && j == 1){
                ans[i][j] = 1;
                continue;
            }
            ans[i][j] = ans[i - 1][j] + ans[i][j - 1];
        }
    }
    cout << ans[21][21] << endl;
    return 0;
}

2.组合问题

1
2
3
4
5
6
7
8
9
10
11
12
#include<iostream>
using namespace std;

int main(){
    long long fin = 1;
    for(int i = 40, j = 1; i > 20; i--, j++){
        fin *= i;
        fin /= j;
    }
    cout << fin << endl;
    return 0;
}

注意：如果是带有障碍物的问题则数学方法将不再适用，可以在方法1的基础上加入条件判断解决

3.有限制的路径方案数

马踏过河问题

image-20210417201534724