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
标签:int,E5%,denominator,numerator,long,--,算法,秋招,刷题 From: https://www.cnblogs.com/kekexxr/p/17344240.html