关键词：数学 动态规划 快速幂
这道题其实是分为两题。
题目一：
这道题我是没有思路的，看了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;
}
};
