luckydog

V1

2022/03/10阅读:41主题:默认主题

Code 62

动态规划

code 62
一个机器人位于一个 m x n 网格的左上角,机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角。问总共有多少条不同的路径?
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/unique-paths 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

题解

代码

int min = Math.min(m -1, n -1);
        long ans = 1;
        for (int i = m + n -2, j = 1; j <= min; i--, j++){
            ans = ans * i / j;
        }
        return (int) ans;
    }

分析

  • 高中排列组合常见题型,解法如上(注意ans类型为long,否则会int范围不够)
  • 可使用dp,滚动数组优化。注意在不使用滚动数组优化时候,行列初始都为1,使用滚动数组之后,可以行滚动或者列滚动(自己感觉,未代码实现)。

分类:

后端

标签:

Java

作者介绍

luckydog
V1