343. 정수는 정수의 합을 분할하고 곱하기 최대화 dp[i] = Math.max(dp[i],Math.max(j*dp[i-j],j*(i-j)));
n， ， 。 。
， n = 2， 1（2 = 1 + 1）； n = 10， 36（10 = 3 + 3 + 4）。
： n 2 58。① dp[i]를 사용하여 정수 i의 최대 곱셈을 표시하면
dp[i]=max{dp[i-1]*1,dp[i-2]*2,...,dp[i-(i-1)]*(i-1)
(i-1) * 1,(i-2) * 2,(i-3)*3,.....(i) * (i-1)}.class Solution {
public int integerBreak(int n) {
int[] dp = new int[n+1];
dp[1] = 1;
for(int i=2;i<=n;i++){
for(int j=1;j<=i-1;j++){
dp[i] = Math.max(dp[i],Math.max(j*dp[i-j],j*(i-j)));
}
}
return dp[n];
}
}②①에서 알 수 있듯이 dp[i]의 상태는 다른 dp[1]로 바뀔 수 있다. dp[i-1]는 얻을 수 있지만 사실은 이렇게 번거롭지 않다. 왜냐하면 이런 정수 분할은 결국 2, 3과 소수로 나누어지기 때문이다.예를 들면 다음과 같습니다.
2:1*1=1;
3:1*2=2; 여기는 dp[2]*1이 아닙니다.
4:2*2=4;
5:2*3=6;
따라서 상태 이동 방정식을
dp[i]=max(dp[i-2]*2,dp[i-3]*3)로 조정한다.class Solution {
public int integerBreak(int n) {
if(n == 2)
return 1;
if(n == 3)
return 2;
int[] dp = new int[n+1];
dp[0] = 0;
dp[1] = 1;
dp[2] = 1;
dp[3] = 2;
int p,q;
for(int i=4;i<=n;i++){
p = Math.max(dp[i-2]*2,(i-2)*2);
q = Math.max(dp[i-3]*3,(i-3)*3);
dp[i] = Math.max(p,q);
}
return dp[n];
}
}참조:https://blog.csdn.net/lml0703/article/details/80058421
class Solution {
public int integerBreak(int n) {
if(n < 4)
return n - 1;
int res = 1;
while(n > 2){
res *= 3;
n = n - 3;
}
if(n == 0)
return res;
if(n == 1)
return (res/3) * 4;// 3 1， 3 1 4
if(n == 2)
res *= n;
return res;
}
}참조:https://www.cnblogs.com/zywscq/p/5415303.html https://blog.csdn.net/will130/article/details/51193736
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
python 문자열 입력으로 모든 유효한 IP 주소 생성(LeetCode 93번 문제)이 문제의 공식 난이도는 Medium으로 좋아요 1296, 반대 505, 통과율 35.4%를 눌렀다.각 항목의 지표로 말하자면 보기에는 약간 규범에 맞는 것 같지만, 실제로도 확실히 그렇다.이 문제의 해법과 의도는 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
