【剑指offer】剪绳子(两种思路)

剪绳子

https://www.nowcoder.com/questionTerminal/57d85990ba5b440ab888fc72b0751bf8?answerType=1&f=discussion

class Solution {
public:
    int cutRope(int number) {
        if(number == 2) return 1;
        if(number == 3) return 2;
       //动态规划, O(n)
        vector<int> res = {0, 1, 2, 3};//数组这里记录的长度是不考虑继续再剪的最长长度,和前面的返回值稍有区别。
        for(int i = 4; i <= number; i++){
            int j = i / 2;
            res.push_back(res[j] * res[i - j]);
        }
        return res[number];
        /*
        找到规律发现,最大乘绩的分法一般就是一堆3和一个2或者两个2的组合
        O(logn)
        int x = number % 3;
        int y = number / 3;
        if(x == 0)
            return (long long) pow(3, y);
        else if(x == 1)
            return 2 * 2 (long long) pow(3, y - 1);
        else
            return 2 * (long long) pow(3, y);
        */
    }
};
全部评论

相关推荐

不愿透露姓名的神秘牛友
07-07 11:30
仁者伍敌:kpi都懒得刷了属于是
点赞 评论 收藏
分享
zYvv:双一流加大加粗再标红,然后广投。主要是获奖荣誉不够,建议开始不用追求大厂,去别的厂子刷下实习。
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务