LeetCode 343. 정수 분할 DP

4286 단어 LeetCode동적 기획

LeetCode 343. 정수 분할 DP


제목.

	343.     
        n,              ,            。             。

   1:

  : 2
  : 1
  : 2 = 1 + 1, 1 × 1 = 1。
   2:

  : 10
  : 36
  : 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。
  :       n     2      58。

    47,378    81,471

사고의 방향

   Fib, n   ,     1-(n-1)     。            ,
 1    n-1。             ,      i/2    ,    ,
     。

코드

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

좋은 웹페이지 즐겨찾기