【leetcode】343. 整数分割(dp)
5036 ワード
タイトルの説明
正の整数nが与えられ、少なくとも2つの正の整数の和に分割され、これらの整数の積を最大化する.取得できる最大積を返します.例1:入力:2出力:1解釈:2=1+1,1× 1 = 1. 例2:入力:10出力:36解釈:10=3+3+4,3× 3 × 4 = 36. 説明:nが2以上58以下であると仮定できます.
問題を解く構想. dp[i i i i]は、整数i i iがいくつかの正の整数に分割された後の積の最大値を表す.dp[i i i]=m a x max(dp[i−j i−j]*j j),(j∈[1,i−1]jin[1,i−1]j∈[1,i−1]j∈[1,i−1]),動的計画に対する「いい感じ」であれば,この状態遷移方程式が考えられるはずである. 境界条件について,dp[i i i]をi i iに初期化した.これは,上記の状態遷移方程式を用いて整数m mの「(m−1)*1」のような分割を得ることができるからである. さらに,2<=x<=3 2<=x<=3 2<=x<=3の場合,上記の状態遷移方程式は正しい結果を出すことができないことを見出した.この2つの小さい数は実際にdp[i i i]=m i n min(dp[i−j i−j]*j j j),(j∈[1,i−1]jin[1,i−1]j∈[1,i−1]j∈[1,i−1])を満たすことが分かったからである.2<=x<=3 2<=x<=3 2<=x<=3 2<=x<=3の場合、dp[x]=x−1 dp[x]=x−1 dp[x]=x−1となり、出力を直接特判すればよい.
ACコード
正の整数nが与えられ、少なくとも2つの正の整数の和に分割され、これらの整数の積を最大化する.取得できる最大積を返します.例1:入力:2出力:1解釈:2=1+1,1× 1 = 1. 例2:入力:10出力:36解釈:10=3+3+4,3× 3 × 4 = 36. 説明:nが2以上58以下であると仮定できます.
問題を解く構想.
ACコード
class Solution {
public:
int Max(int a,int b){
return a>b ? a : b;
}
int integerBreak(int n) {
vector<int>dp(n+1,0);
if(n<=3) return n-1;
for(int i=1;i<=n;i++) dp[i]=i;
for(int i=2;i<=n;i++){
for(int j=1;j<i;j++){
dp[i]=Max(dp[i],dp[i-j]*j);
}
}
return dp[n];
}
};