数据结构学习 jz14剪绳子

关键词：数学 动态规划 快速幂

这道题其实是分为两题。

题目一：

这道题我是没有思路的，看了k神的答案才知道有数学的方法。

方法一：

数学：其实中间的推导我没看，我服了。

思路：

复杂度计算：

时间复杂度O(1)

空间复杂度O(1)

代码：

看了k神的答案自己写的

class Solution {
public:
    int cuttingBamboo(int bamboo_len) {
        if(bamboo_len<=3) return bamboo_len-1;
        int a=bamboo_len/3 ,b=bamboo_len%3;
        if(b==0) return pow(3,a);
        if(b==1) return pow(3,a-1)*4;
        return pow(3,a)*2;
    }
};

方法二：

动态规划。

是我在看官方题解里面得到的思路。但比数学方法慢很多。

思路：

dp状态：

dp[i]如果竹子长为i，砍竹子可以得到的最大乘积结果。

复习知识点：

无后效性：dp[i]只与前面的dp结果有关，不与前面dp求得的过程有关。

最优子结构：dp[i]可以由dp[0...i-1]推出。

?转移方程：

dp[i]=max(dp[1..i-1]*dp[i-1...1])

即dp[i]必须要被砍成两半，但是这两半要怎么选，要一个一个试过才知道（第二个for循环）。

比如：i==6。砍的方法有dp[5]*dp[1]、dp[4]*dp[2]、dp[3]*dp[3]，前面的dp已经算出了他们的最优值，拿他们的乘积比较即可。

初始化：

这个dp初始化是为了后面的dp专门设计的

? ? ? ? dp[0]=0;//0
? ? ? ? dp[1]=1;//1
? ? ? ? dp[2]=2;//2
? ? ? ? dp[3]=3;//3

复杂度计算：

时间复杂度O(n*n)

空间复杂度O(n)

代码：

这里我在第二个for循环减少了一半开销。因为dp[5]*dp[1]和dp[1]*dp[5]一样的。

class Solution {
public:
    int cuttingBamboo(int bamboo_len) {
        if(bamboo_len<=3) return bamboo_len-1;
        vector<int> dp(bamboo_len+1);
        dp[0]=0;//0
        dp[1]=1;//1
        dp[2]=2;//2
        dp[3]=3;//3
        for(int i=4;i<=bamboo_len;++i)//时间复杂度O(n*n)
        {
            for(int j=1;j<=i/2+i%2;++j)//只用找一半
            {
                dp[i]=max(dp[i],dp[i-j]*dp[j]);
            }
        }
        return dp[bamboo_len];
    }
};

题目二：

数学、快速幂

这道题和第一题的区别就是长度的范围扩大了，如果用数学法，用stl里的pow求3为底的结果会爆炸，所以需要快速幂来取模。

思路：

第一题的数学+快速幂+求模?

复杂度计算：

时间复杂度O(logn) 快速幂

空间复杂度O(1)

代码：

class Solution {
public:
    int MOD=1000000007;
    long long my_pow(int a,int n)
    {
        long long res=1;
        long long rex=a;
        while(n)
        {
            if(n&1)
            {
                res=res*rex%MOD;
            }
            rex=rex*rex%MOD;
            n=n>>1;
        }
        return res;
    }
    int cuttingBamboo(int bamboo_len) {
        if(bamboo_len<=3) return bamboo_len-1;
        
        int a=bamboo_len/3,b=bamboo_len%3;
        long long res;
        if(b==0) 
        {
            res = my_pow(3,a);
            return res;
        }
        
        if(b==1) 
        {
            res = my_pow(3,a-1);
            res=res*4%MOD;
            return res;
        }
        res = my_pow(3,a);
        res=res*2%MOD;
        return res;
    }
};