343 整数拆分

  1. class Solution {
  2.     public int integerBreak(int n) {
  3.         if (n < 2)
  4.             return 0;
  5.         if (n == 2)
  6.             return 1;
  7.         if (n == 3)
  8.             return 2;
  10.         // 当整数的值大于3时 
  11.         int[] dp = new int[n + 1];
  12.         dp[0] = 0; dp[1] = 1; dp[2] = 2; dp[3] = 3;
  13.         int max = 0;
  15.         for (int i = 4; i <= n; ++i) {
  16.             max = 0;
  17.             for (int j = 1; j <= i / 2; ++j) {
  18.                 int temp = dp[j] * dp[i -j];
  19.                 if (temp > max)
  20.                     max = temp;
  22.                 dp[i] = max;
  23.             }
  24.         }
  26.         return dp[n];
  27.     }
  28. }