题目描述
给你一根长度为n的绳子，请把绳子剪成m段 (m和n都是整数，n>1并且m>1)每段绳子的长度记为k[0],k[1],…,k[m].请问k[0]k[1]…*k[m]可能的最大乘积是多少？
解法
典型的动态规划问题，将最终最值问题转换为由各个小问题的最值堆叠起来，并且在这个过程中存储各个小问题的最值。 我们可以将这段绳子最大乘积的问题进行转换：先将他切割为两部分，假设切割之后这两部分长度的最大值都是已知的，则当前切法的最值就可以直接求出，所以遍历所有切法，依次进行比较，最后得出这之中的最大值。那么问题就可缩小为求这更小的两部分长度的最值问题。 因此，我们可以设dp[n]表示长度为n的绳子的最大乘积。则有dp[n]=max(dp[i]*dp[n-i]) 1<=i<n;
代码
func inciseRope(n int)int{
dp:=make([]int,n+1,n+1)
if n<=4{
return n
}
//1~4本身不切割时值最大。
dp[0] = 0
dp[1] = 1
dp[2] = 2
dp[3] = 3
dp[4] = 4
for i:=5;i<=n;i++{
for j:=1;j<=(n/2);j++{
temp := dp[j]*dp[i-j]
if temp>dp[i]{
dp[i] = temp
}
}
}
return dp[n]
}
总结
动态规划的特征：求最优解，并且最优解可以通过将大问题拆分从小问题，然后由小问题的最优解组合得出大问题的最优解，从上往下分析问题，从下往上解决问题。
类似斐波那契函数
f(n)=f(n-1)+f(n-2); 最终都可以由f(1)和f(2)堆叠起来求出结果，而且从上往下递归会造成很多重复计算，从下往上叠加可以不重复；
