Java面试-动态规划与组合数

2023-05-30 17:37:24 java 面试

近在刷力扣上的题目,刷到了65不同路径,当初上大学的时候,曾在hihocoder上刷到过这道题目,但是现在已经几乎全忘光了,大概的知识点是动态规划,如今就让我们一起来回顾一下。

从题目说起

题目原文是:

一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为“Start” )。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为“Finish”)。
问总共有多少条不同的路径?



例如,上图是一个7 x 3 的网格。有多少可能的路径?
说明:m 和 n 的值均不超过 100。
示例 1:
输入: m = 3, n = 2
输出: 3
解释:
从左上角开始,总共有 3 条路径可以到达右下角。
  1. 向右 -> 向右 -> 向下
  2. 向右 -> 向下 -> 向右
  3. 向下 -> 向右 -> 向右


示例 2:
输入: m = 7, n = 3
输出: 28

正向思路

我们先按照正常思路来想一下,当你处于起点时,你有两个选择,向右或者向下,除非你处于下面一排或者右边一列,那你只有一种选择(比如处于下面一排,你只能往右),其他位置,你都有两种选择。

因此,我们就根据这个思路,可以写出代码:

class Solution {
    public int uniquePaths(int m, int n) {
        // 特殊情况:起点即终点
        if (m == 1 && n == 1) {
            return 1;
        }
        // 当前处于(1,1),终点为(m,n)
        return walk(1, 1, m, n);
    }

    public int walk(int x, int y, int m, int n){
        // 已经处于终点
        if (x >= m && y >= n) {
            return 0;
        }
        // 处于下面一排或者右边一列
        if (x >= m || y >= n) {
            return 1;
        }
        // 往下走,有多少种走法
        int down = walk(x, y + 1, m, n);
        // 往右走,有多少种走法
        int right = walk(x + 1, y, m, n);
        // 从当前(x,y)出发,走到(m,n),共有多少种走法
        return down + right;
    }
}

相关文章