Leetcode - Integer Break

1274 단어
My code:
public class Solution {
    public int integerBreak(int n) {
        if (n <= 0) {
            return 0;
        }
        
        int[] dp = new int[n + 1];
        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            int begin = 1;
            int end = i - 1;
            int max = 0;
            while (begin <= end) {
                int n1 = dp[begin] * end;
                int n2 = dp[begin] * dp[end];
                int n3 = begin * end;
                int n4 = begin * dp[end];
                max = Math.max(max, Math.max(n1, Math.max(n2, Math.max(n3, n4))));
                begin++;
                end--;
            }

            dp[i] = max;
        }
        
        return dp[n];
    }
}

나의 사상은perfect square라는 제목과 매우 유사하다.8이라면 1, 7, 2, 6, 3, 5, 4, 4로 구성할 수 있다.그리고 1, 2, 3, 4, 5, 6, 7은 다시 세분화하거나 구분하지 않아도 된다.그래서 각 그룹에 대해 네 가지 결과가 있을 수 있고 가장 큰 것을 내놓으면 된다.예를 들어 3, 5는 3 * 5 (1 * 2) * 5 3 * (2 * 3) (1 * 2) * (2 * 3)
최대치가 18이니까 dp[8]=18.
time complexity : O(n ^ 2)
그리고 답은 O(n)의 해법이 있다고 한다.https://discuss.leetcode.com/topic/55120/my-simple-dp-solution-o-n
보자마자 규칙을 찾았다.재미 없어요.그리고 O(log n) 해법도 있고 수학 게임도 한다고 합니다.별로 재미 없어요.연구하지 않겠소.
Anyway, Good luck, Richardo! -- 08/27/2016

좋은 웹페이지 즐겨찾기