动态规划-剪绳子

题目描述
给你一根长度为n的绳子，请把绳子剪成整数长的m段（m、n都是整数，n>1并且m>1，m<=n），每段绳子的长度记为k[1],...,k[m]。请问k[1]x...xk[m]可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。
解题思路：
先进行举例说明：
2===1 $图片说明$ 1=1
3===1 $图片说明$ 2=2
4===2 $图片说明$ 2=4
5===2 $图片说明$ 3=6
6===3 $图片说明$ 3=9
7===3 $图片说明$ 4=3 $图片说明$ 2 $图片说明$ 2=12
由此可看，从5开始，后续的子绳子长度都有3.可能有2也可能没有
那我们来构造动态规划的答案
我们求长为i的绳子的最大乘积。
有两种情况：
一：前一个里有2，则可以直接把2变成3，也可以结合一个3形成两个2，求乘积最大值即可
二：前一个里没有2，则只能结合3变成两个2，求乘积

针对于2和3和4 的特殊情况要进行特殊处理赋值。
因为4里没有3，但是也有2.所以要不就特殊处理，因为只有一个。否则需要判断是否含有3.计算量更大

上一篇找规律结果：语言：Java 运行时间： 12 ms 占用内存：9532K
动态规划结果：语言：Java 运行时间： 11 ms 占用内存：9780K

动态规划代码如下：注释部门为找规律代码

public class Solution {
    public int cutRope(int target) {
//         //12ms 9532kb  直接找规律
//         if(target==2){
//             return 1;
//         }else if(target==3){
//             return 2;
//         }else{
//             int n1=target/3;
//             int n2=target%3;
//             if(n2==0){
//                 return (int)Math.pow(3,n1);
//             }
//             else if(n2==1){
//                 return 2*2*(int)Math.pow(3,n1-1);
//             }else{
//                 return 2*(int)Math.pow(3,n1);
//             }
//         }
        if(target==2){
            return 1;
        }
        else if(target==3){
            return 2;
        }
        else if(target==4){
            return 4;
        }
        else if(target==5){
            return 6;
        }
        else{
            int[] ans=new int[target];
            ans[1]=1;
            ans[2]=2;
            ans[3]=4;
            ans[4]=6;
            for(int i=5;i<target;i++){
                if(ans[i-1]%2==0){
                    ans[i]=Math.max(ans[i-1]/2*3,ans[i-1]/3*4);
                }
                else{
                    ans[i]=ans[i-1]/3*4;
                }
            }
            return ans[target-1];
        }

    }
}