LeetCode 62. Unique Paths (规律做法)

た入场券 2024-04-17 23:23 64阅读 0赞

题目描述：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjUyNjE5_size_16_color_FFFFFF_t_70][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjUyNjE5_size_16_color_FFFFFF_t_70 1][]

思考了一下，发现其实就两种走法，一个向右一个向下，那，一共要走m+n-2格子也知道了，那其实就是高中数学的填空问题嘛，比如说m+n-2个格子依次排开，我们挑选向下的走法放在哪个格子里，转换为数学公式就是![C\_\{m+n-2\}^\{n-1\}][C_m_n-2_n-1]

没毛病吧

class Solution {
    public:
        int uniquePaths(int m, int n) {
            //如果我没猜错的话Cmn就是答案（n是上标）,一共走m+n-2步,向下n-1步，那么n-1个元素放在m+n-2个位置
            long result = 1;
            int total = m+n-2;
            int times = m > n ? (n-1) : (m-1);
            //直接拿times-=会影响循环 
            int tmp = times;
            //分子 ，不用分子直接除会有小数 
            int son = 1;
            for(int i = 0; i < times; i++){
                result *= total;
                son *= tmp;
                total -= 1;
                tmp -= 1;
            }
            return result/son;
        }
    };

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjUyNjE5_size_16_color_FFFFFF_t_70 2][]

有点奇怪的就是他给了个案例说result取int型不够，我在本地跑这个例子没问题，改了long就过了。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjUyNjE5_size_16_color_FFFFFF_t_70]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/17/c79913624e3147feb0b1b06ffc4d0db1.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjUyNjE5_size_16_color_FFFFFF_t_70 1]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/17/84699e9432644a7a8fa25bb57a36e7fa.png
[C_m_n-2_n-1]: https://private.codecogs.com/gif.latex?C_%7Bm&plus;n-2%7D%5E%7Bn-1%7D
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjUyNjE5_size_16_color_FFFFFF_t_70 2]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/17/e58e4afab0524bbb8f04842afc9826ed.png