题目

image.png

思路

  • 思路一：暴力递归，对于每个大于1的数字来说，它都可以有若干个2或3组成，并且拆成2或3的积最大，因此，递归的时候我们可以将数拆分为n-2或n-3，取它们的最大值
  • 思路二：备忘录
  • 思路三：动态规划，定义dp[i]表示切分后最大能表示的数，dp[i] = Math.max(dp[i-2]2,dp[i-3]3)

  • 思路四：优化dp数组的动态规划，通过观察dp数组即可

    代码

    1.   //1.暴力递归
    2.   public int cuttingRope(int n) {
    3.       if (n == 2 || n == 1) return 1;
    4.       if (n == 3) return 2;
    5.       return recur(n);
    6.   }
    7.   //当n > 1时，由于每个数由若干个2、3组成，所以每次每个数可以分割为2或3，并且拆成2或3的积最大
    8.   public int recur(int n) {
    9.       if (n <= 3) return n;
    10.       return Math.max(recur(n - 2) * 2, recur(n - 3) * 3);
    11.   }
    13.   //2.备忘录
    14.   int[] dp;
    15.   public int cuttingRope(int n) {
    16.       if (n == 2 || n == 1) return 1;
    17.       if (n == 3) return 2;
    18.       dp = new int[n + 1];
    19.       return recur(n);
    20.   }
    22.   public int recur(int n) {
    23.       if (n <= 3) return n;
    24.       if (dp[n] != 0) return dp[n];
    25.       dp[n] = Math.max(recur(n - 2) * 2, recur(n - 3) * 3);
    26.       return dp[n];
    27.   }
    29.   //3.动态规划
    30.   public int cuttingRope(int n) {
    31.       if (n == 2 || n == 1) return 1;
    32.       if (n == 3) return 2;
    33.       //dp[i]表示当前i可分割后最大值
    34.       int[] dp = new int[n + 1];
    35.       dp[1] = 1; dp[2] = 2; dp[3] = 3;
    36.       for(int i = 4; i <= n; i++) {
    37.           dp[i] = Math.max(dp[i - 2] * 2, dp[i - 3] * 3);
    38.       }
    39.       return dp[n];
    40.   }
    42.   //4.由于每次只用到了前2个变量，所以可以优化dp数组
    43.   public int cuttingRope(int n) {
    44.       if (n == 2 || n == 1) return 1;
    45.       if (n == 3) return 2;
    46.       int p1 = 1, p2 = 2, p3 = 3;
    47.       for(int i = 4; i <= n; i++) {
    48.           int t = p3;
    49.           p3 = Math.max(p2 * 2, p1 * 3);
    50.           p1 = p2;
    51.           p2 = t;
    53.       }
    54.       return p3;
    55.   }

    剪绳子