剑指offer-67-剪绳子

剪绳子

http://www.nowcoder.com/questionTerminal/57d85990ba5b440ab888fc72b0751bf8

思路

不失一般性,首先想到dp,然后考虑状态转移方程
dp一般开始考虑数学归纳法: 0 1 2 3直接输出,4=2+2 ,5=2+ 3 ,6=3+3,7=3+4
假设c=a+b>=2sqrt(ab),当且仅当a==b时取等号。偶数直接分两半,奇数一个向下取整,一个向上取整。
这是两个数的时候,n个数,a1+a2+.....aN>=1/nsqrt(a1*a2....aN)
进一步发现:最终都可以分解为2和3了,并且3越多,乘积越大。
上面归纳3越多值越大是我看评论区的,真实情况是dp[i]=max(dp[i-2]2,dp[i-3]3);
参考3越多写了如下代码,为了炫技也写了只有一行的java代码

代码

switch写法

public class Solution {
    public int cutRope(int target) {
        switch (target%3){
                case 0:return (int)Math.pow(3,target/3);
                case 1:return (int)Math.pow(3,target/3-1)*4;
                case 2:return (int)Math.pow(3,target/3)*2;
        }
        return 0;
    }
}

一行代码

public class Solution {
    public int cutRope(int target) {
        return target%3==0?(int)Math.pow(3,target/3):
        (target%3==1?(int)Math.pow(3,target/3-1)*4:(int)Math.pow(3,target/3)*2);
    }
}
剑指offer与数据结构 文章被收录于专栏

本专栏包括剑指offer题目和一些刷题用的数据结构,单调栈,树状数组,差分数组,后面还会更新红黑树等较为复杂的数据结构

全部评论

相关推荐

评论
点赞
收藏
分享

创作者周榜

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