dp-분할 정수 문제
343. 정수 분할 M(승적 최대화)
정수 n을 지정하여 최소 두 개의 정수의 합으로 나누고 정수의 곱셈을 최대화합니다.네가 얻을 수 있는 최대 곱셈을 되돌려라.
max 함수는 initializer 를 사용할 수 있습니다list, 여러 개의 수를 구하는 데 사용되는 최치;
class Solution {
public:
int integerBreak(int n) {
vector dp(n+1);
dp[1] = dp[2] = 1;
for(int i = 3; i <= n; i++){ for(int j = 1; j <= i-1;j++){ dp[i] = max({dp[i],dp[j]*dp[i-j],j*dp[i-j],dp[j]*(i-j),j*(i-j)}); } } return dp[n]; } }; 279. 전체 제곱(제곱수로 정수 분할) M
정수 n을 정하고 완전한 제곱수 (예:
1, 4, 9, 16, ... 를 찾아서 그것들의 합을 n과 같다.너는 완전한 제곱수의 개수를 최소화해야 한다.약간 가방 문제 같다: 복잡도 O(N^1.5);
class Solution {
public:
int numSquares(int n) {
vector<int> dp(n+1,0x3f3f3f3f);
dp[0] = 0;
for(int i = 1; i*i <= n; i++)
dp[i*i] = 1;
for(int i = 1; i <= n; i++)
for(int j = 0;j*j <=i; j++)
dp[i] = min(dp[i],dp[j*j]+dp[i-j*j]);
return dp[n];
}
};이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
