정수 분할 - 동적 계획법

제목: 정수 n을 최대 m의 분할 방안 개수로 무질서하게 분할하여 모든 분할 방안이 중복되지 않도록 합니다.
예를 들어 n=5, m=5, 대응하는 분할 방안은 다음과 같다. 5=5 = 4+1 5 = 3+2 5 = 3+1 + 1 5 = 2+2 + 1 5 = 2+1 + 1 + 1 + 1 5 = 1+1 + 1 + 1 + 1 사고방식: 예제에서 알 수 있듯이 순서는 결과에 영향을 주지 않으며 우리는 동적 기획법으로 문제를 해결한다.그룹 dp[n+1][m+1]을 만듭니다.그 중에서 dp[i][j]는 정수 i가 최대 j개의 숫자로 나누어진 방안 수를 가리킨다.꼭 j개로 뜯어야 하는 것이 아니라 1~j개로 뜯어야 한다는 것을 주의해라.다음은 1.j=1 또는 i=1이면 숫자 1을 n점으로 나누거나 n을 1점으로 나누는 것을 의미한다.결과는 다 1, 2.i가 j보다 작으면 분할 결과의 모든 숫자가 0보다 크기 때문에 나머지 j는 쓸모가 없다.이때 dp[i][j]=dp[i][i] 3.i=j, 여기서 우리는 1~j를 분리하여 1에서 j-1과 j로 나눈다.i를 j로 나누어 1로 나눈다는 뜻이다.최대 j-1부로 뜯기 2.꼭 j부로 뜯어낼게요.전자는 dp[i][j-1]이고 후자는 1이라는 것을 쉽게 알 수 있다. 왜냐하면 i=j. 이때 dp[i][j]=1+dp[i][j-1]4.i>j, 이때 제3조와 유사하면 우리는 1~j를 1에서 j-1과 j로 나눈다.전자는 dp[i][j-1]이다.후자는 계속 분석했다. 이때 i>j는 반드시 j분으로 나누어야 한다. 그러면 우리는 먼저 j분 1로 나눌 수 있다. 이때의 합은 j이고 나머지 숫자는 i-j가 있다. 우리는 남은 숫자 i-j를 무작위로 j분으로 나누면 결과가 된다.dp[i][j]=dp[i-j][j]+dp[i][j-1] 예를 들어 dp[5][4]를 구하면 먼저 dp[3]=5를 4부로 나누고 우리는 1부에 1을 주고 이때 1이 남는다. 1을 최대 4부로 나누면 dp[1][4]이다. 그 결과는 1(순서를 고려하지 않기 때문이다)이다.

public class Solution{

    public  int integerhuafen(int n, int m) {

        int dp[][] = new int[n + 1][m + 1];
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= m; j++ ){
                if(i == 1 || j == 1){
                    dp[i][j] = 1;
                }else if (i == j) {
                    dp[i][j] = 1 + dp[i][j - 1];
                }else if (i < j) {
                    dp[i][j] = dp[i][i];
                }else {
                    dp[i][j] = dp[i - j][j] + dp[i][j - 1];
                }
            }
        }
        return dp[n][m];
    }
}