剑指 Offer 14- I. 剪绳子(Java)（动态规划）

题目链接：剑指 Offer 14- I. 剪绳子
题目描述：

动态规划，绳子只能分2或者分3才是最优解，最好分若干个3加一个2或者全是3，因为如果分4就跟两个2和1，3一样，所以没必要考虑吧。

class Solution {
    public int cuttingRope(int n) {
        if(n==0||n==1||n==2)return 1;
        if(n==3)return 2;
        int[] dp=new int[n+1];
        dp[1]=1;
        dp[2]=2;
        dp[3]=3;
        for (int i = 4; i < n+1; i++) {
            dp[i]=Math.max(dp[i-3]*3,dp[i-2]*2);
        }
        return dp[n];
    }
}