题解 | #剪绳子#

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @return int整型
     */
    public int cutRope (int n) {
        // write code here
        int [] dp=new int [n+1];
        dp[0]=1;
        dp[1]=1;
        for(int i=2;i<=n;i++){
            for(int j=1;j<i;j++){
                dp[i]=Math.max(dp[i],(Math.max(j,dp[j]))*(Math.max(i-j,dp[i-j])));
            }
        }
        return dp[n];
    }
}

//明确递归数组的意义，dp【n】代表什么意思。dp【n】代表n长度的绳子，分为m段最长为dp【n】。
int[] dp =new int [n];
//初始化递归数组,要想清楚他们的依赖关系。在此处    i=j+(i-j)
//j和i-j都不能再拆了 dp[i]=j*(i-j);
//j能拆，i-j不能拆 dp[i]=dp[j]*(i-j);
//j不能拆，i-j能拆  dp[i]=j*dp[i-j];
//j和i-j都能拆 dp[i]=dp[j]*dp[i-j];，         dp【i】=max（dp[i],max(j,dp[j])*max(i-j,dp[i-j])）


dp[1]=1;
//确定递归函数,返回
for(int i=2;i<=n;i++){
            for(int j=1;j<i;j++){
                dp[i]=Math.max(dp[i],(Math.max(j,dp[j]))*(Math.max(i-j,dp[i-j])));
            }
        }
        return dp[n];