题解 | #剪绳子#

·import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param n int整型
     * @return int整型
     */
    public int cutRope (int n) {
        // write code here
        if (n == 0) {
            return 0;
        }
        if (n == 1) {
            return 1;
        }
        if (n == 2) {
            return 2;
        }
        if (n == 3) {
            return 3;
        }
        int[] db = new int[n + 1]; //长度为i的身子截取后乘机的最大值
        db[0] = 0;
        db[1] = 1;
        db[2] = 2;
        db[3] = 3;
        for (int i = 4; i <= n; i++) { //求出第i长的身子的最大乘机
            int max = 0;
            for (int j = 0; j <= i / 2; j++) {
                max = Math.max(max, db[j] * db[i - j]);
            }
            db[i] = max;
        }
        return db[n];
    }
}