秋招算法刷题-JZTXT

1.组合数计算不溢出方法：https://programmercarl.com/0062.%E4%B8%8D%E5%90%8C%E8%B7%AF%E5%BE%84.html#%E6%80%9D%E8%B7%AF

求组合的时候，要防止两个int相乘溢出！所以不能把算式的分子都算出来，分母都算出来再做除法。

class Solution {
public:
    int uniquePaths(int m, int n) {
        long long numerator = 1; // 分子
        int denominator = m - 1; // 分母
        int count = m - 1;
        int t = m + n - 2;
        while (count--) {
            numerator *= (t--);
            while (denominator != 0 && numerator % denominator == 0) {
                numerator /= denominator;
                denominator--;
            }
        }
        return numerator;
    }
};

动态规划没写出来的题目（力扣）：

（1）  96. 不同的二叉搜索树
（2）  1049. 最后一块石头的重量 II