정수 분할 - 동적 계획법
6804 단어 데이터 구조와 알고리즘
예를 들어 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];
}
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
두 갈래 나무의 깊이가 두루 다니다텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
