dp-整数分割問題(理論解析)
3136 ワード
原文住所:http://www.cnblogs.com/wanghetao/archive/2013/11/25/3442192.html
説明
整数分割は古典的な問題です.次の要件を完了するためにプログラムを書いてください.
入力
各入力セットは2つの整数nとkである.(1 <= n <= 50, 1 <= k <= n)
しゅつりょく
入力されたn,kについて;
1行目:nをいくつかの正の整数の和に分割する分割数.
2行目:nをk個の正の整数の和に分割する分割数.
3行目:nを最大数kを超えない分割数に分割する.
4行目:nをいくつかの奇正整数の和に分割する分割数.
5行目:nをいくつかの異なる整数の和に分割する分割数.
6行目:空の行を印刷
サンプル入力
サンプル出力
ヒント
サンプル出力プロンプト:
1.5をいくつかの正の整数の和に分割する.5、4+1、3+2、3+1+1、2+2+1、2+1+1、1+1+1+1
2.5を2つの正の整数の和に分けたもの:3+2,4+1
3.5を最大数が2を超えないように分割する:1+1+1+1,1+1+2,1+2+2
4.5をいくつかの奇正整数の和に分割する:5,1+1+3,1+1+1+1
5.5をいくつかの異なる整数の和に分割する:5,1+4,2+3
この問題はダイナミックプランニング(Dynamic Programming)メソッドを使用して解決します.
nをいくつかの正の整数の和に分割する分割数を求める
1.分割された複数の整数が同一である場合
dp[i][j]をiをj以下に分割する分割数とする
(1)i(2)i>jの場合,分割にjが含まれているか否かによって2つに分けることができる.区分にjが含まれている場合、区分案数はdp[i-j][j]である.分割数にjが含まれていない場合は、iをj−1以下に分割する分割数に相当し、dp[i][j−1]となる.したがって、i>jの場合、dp[i][j]=dp[i-j][j]+dp[i][j-1];
(3)i=jの場合、分割にjが1つしか含まれていない場合、分割にjが含まれていない場合は、iをj-1以下に分割する分割数に相当する.このときdp[i][j]=1+dp[i][j-1]となる.
dp[n][n]は問題1を解決することができ、dp[n][k]はnを最大数kを超えない分割数に分割し、問題3を解決することができることを示す.
2.分割された正の整数が異なる必要がある場合
dp[i][j]をiをjを超えない異なる整数に分割する分割数とする
(1)i(2)i>jの場合,分割にjが含まれているか否かによって2つに分けることができる.区分にjが含まれている場合、残りの区分の最大はj-1であり、シナリオ数はdp[i-j][j-1]である.分割にjが含まれていない場合は、iをj−1以下に分割する分割数に相当し、dp[i][j−1]となる.したがって、i>jの場合、dp[i][j]=dp[i-j][j-1]+dp[i][j-1];
(3)i=jの場合、分割にjが1つしか含まれていない場合、分割にjが含まれていない場合は、iをj-1以下に分割する分割数に相当する.このときdp[i][j]=1+dp[i][j-1]
dp[n][n]は、nを異なる整数に分割する分割数を表し、問題を解決することができる.
二nをk個の整数に分割する分割数
dp[i][j]をiをj個の整数に分割する分割数とする.
(1)i(2)i=jの場合、iはi個1の和に分けることができ、dp[i][j]=1;
(3)i>jであれば、分割数に1が含まれているかどうかによって2種類に分けることができる:分割数に1が含まれている場合は、「エッジカット法」を用いてj個の分割をそれぞれ1つ切り取り、問題をi-jのj-1個の分割数に変換し、dp[i-j][j-1]とすることができる. 分割に1が含まれていない場合は、「エッジカット法」を用いてj個の分割数の一番下の数を切り取り、題目をi-jを求めるj個の分割数に変換し、dp[i-j][j]とする.したがってi>jではdp[i][j]=dp[i-j][j-1]+dp[i-j][j]となる.
dp[n][k]は、nをk個の整数に分割する分割数であり、問題2を解決することができる.
三nをいくつかの正奇数の和に分ける区分数
f[i][j]はiをj個の奇数の和に分割する分割数、g[i][j]はiをj個の偶数の和に分割する分割数とする.
エッジカット法を用いてg[i][j]のj個の区分をすべて1削除し,f[i-j][j]を得ることができるので,
g[i][j] = f[i-j][j].
f[i][j]には1を含む分割スキームと1を含まない分割スキームがある.1を含む分割スキームについては、1の分割を除去し、「i−1をj−1個の奇数の和に分割する分割数」、すなわちf[i−1][j−1]に変換することができる.1を含まない分割スキームでは、エッジカット法を用いてj個の分割ごとに1を削除し、「i−jをj個の偶数の和に分割する分割数」、すなわちg[i−j][j]に変換することができる.
だからf[i][j]=f[i-1][j-1]+g[i-j][j]です.
f[n][0]+f[n][1]+......+f[n][n]はnをいくつかの奇数に分割する分割数であり,問題4の答えである.
参考:[1] http://blog.csdn.net/a83610312/article/details/12685653
[2] http://www.cnblogs.com/jackge/p/3163835.html
実装コード:
ネット上で本題の実現コードはすべてC言語で書いたもので、しかも計算が多すぎる.本来はユーザーの入力規模nに基づいて、直接n*nの行列を計算すればよいが、ネット上のコード計算はN*Nであり、Nは予め設定された値であり、しかもnよりずっと大きく、このようにプログラムの速度に影響を及ぼす.
説明
整数分割は古典的な問題です.次の要件を完了するためにプログラムを書いてください.
入力
各入力セットは2つの整数nとkである.(1 <= n <= 50, 1 <= k <= n)
しゅつりょく
入力されたn,kについて;
1行目:nをいくつかの正の整数の和に分割する分割数.
2行目:nをk個の正の整数の和に分割する分割数.
3行目:nを最大数kを超えない分割数に分割する.
4行目:nをいくつかの奇正整数の和に分割する分割数.
5行目:nをいくつかの異なる整数の和に分割する分割数.
6行目:空の行を印刷
サンプル入力
5 2サンプル出力
7
2
3
3
3
ヒント
サンプル出力プロンプト:
1.5をいくつかの正の整数の和に分割する.5、4+1、3+2、3+1+1、2+2+1、2+1+1、1+1+1+1
2.5を2つの正の整数の和に分けたもの:3+2,4+1
3.5を最大数が2を超えないように分割する:1+1+1+1,1+1+2,1+2+2
4.5をいくつかの奇正整数の和に分割する:5,1+1+3,1+1+1+1
5.5をいくつかの異なる整数の和に分割する:5,1+4,2+3
この問題はダイナミックプランニング(Dynamic Programming)メソッドを使用して解決します.
nをいくつかの正の整数の和に分割する分割数を求める
1.分割された複数の整数が同一である場合
dp[i][j]をiをj以下に分割する分割数とする
(1)i
(3)i=jの場合、分割にjが1つしか含まれていない場合、分割にjが含まれていない場合は、iをj-1以下に分割する分割数に相当する.このときdp[i][j]=1+dp[i][j-1]となる.
dp[n][n]は問題1を解決することができ、dp[n][k]はnを最大数kを超えない分割数に分割し、問題3を解決することができることを示す.
2.分割された正の整数が異なる必要がある場合
dp[i][j]をiをjを超えない異なる整数に分割する分割数とする
(1)i
(3)i=jの場合、分割にjが1つしか含まれていない場合、分割にjが含まれていない場合は、iをj-1以下に分割する分割数に相当する.このときdp[i][j]=1+dp[i][j-1]
dp[n][n]は、nを異なる整数に分割する分割数を表し、問題を解決することができる.
二nをk個の整数に分割する分割数
dp[i][j]をiをj個の整数に分割する分割数とする.
(1)i
(3)i>jであれば、分割数に1が含まれているかどうかによって2種類に分けることができる:分割数に1が含まれている場合は、「エッジカット法」を用いてj個の分割をそれぞれ1つ切り取り、問題をi-jのj-1個の分割数に変換し、dp[i-j][j-1]とすることができる. 分割に1が含まれていない場合は、「エッジカット法」を用いてj個の分割数の一番下の数を切り取り、題目をi-jを求めるj個の分割数に変換し、dp[i-j][j]とする.したがってi>jではdp[i][j]=dp[i-j][j-1]+dp[i-j][j]となる.
dp[n][k]は、nをk個の整数に分割する分割数であり、問題2を解決することができる.
三nをいくつかの正奇数の和に分ける区分数
f[i][j]はiをj個の奇数の和に分割する分割数、g[i][j]はiをj個の偶数の和に分割する分割数とする.
エッジカット法を用いてg[i][j]のj個の区分をすべて1削除し,f[i-j][j]を得ることができるので,
g[i][j] = f[i-j][j].
f[i][j]には1を含む分割スキームと1を含まない分割スキームがある.1を含む分割スキームについては、1の分割を除去し、「i−1をj−1個の奇数の和に分割する分割数」、すなわちf[i−1][j−1]に変換することができる.1を含まない分割スキームでは、エッジカット法を用いてj個の分割ごとに1を削除し、「i−jをj個の偶数の和に分割する分割数」、すなわちg[i−j][j]に変換することができる.
だからf[i][j]=f[i-1][j-1]+g[i-j][j]です.
f[n][0]+f[n][1]+......+f[n][n]はnをいくつかの奇数に分割する分割数であり,問題4の答えである.
参考:[1] http://blog.csdn.net/a83610312/article/details/12685653
[2] http://www.cnblogs.com/jackge/p/3163835.html
実装コード:
ネット上で本題の実現コードはすべてC言語で書いたもので、しかも計算が多すぎる.本来はユーザーの入力規模nに基づいて、直接n*nの行列を計算すればよいが、ネット上のコード計算はN*Nであり、Nは予め設定された値であり、しかもnよりずっと大きく、このようにプログラムの速度に影響を及ぼす.