個数制限がない場合
n種から制限なく重複を許してr個選ぶ組合せの総数nHrはn+r-1個の枠に入れるn-1個の種類を分ける区切りの場所の組合わせの総数と等しいので、
(n+r-1)C(n-1) = (n+r-1)Crで求められる。
int factorial(int n)
{
int x = 1;
for (int i = n; i > 0; i--)
{
x *= i;
}
return x;
}
int H(int n, int r)
{
// (n+r-1)Cr
return factorial(n + r - 1) / (factorial(r) * factorial(n - 1));
}
個数制限がある場合
nHrは
- n種類目が少なくとも1つ選ばれる場合：
nH(r-1)(それぞれの組み合わせにn種類目が1つ加わる) - n種類目が1つも選ばれない場合:
(n-1)Hr(残りのn-1種類からr個選ぶ)
の和として表すこともでき、 漸化式 H(n, r) = H(n, r-1) + H(n-1, r) が成り立つ。
int H(int n, int r)
{
if (n <= 0 || r < 0)
{
return 0;
}
if (n == 1 || r == 0)
{
return 1;
}
return H(n, r - 1) + H(n - 1, r);
}
n種類目が少なくとも1つ選ばれるということはn種類目から1 <= i <= r個選ばれ、n-1種類目までからr-i個選ばれると考えることもできるので、
合わせて H(n, r) = Σ(0 <= i <= r) H(n - 1, r-i) で求めることもでき、このループの条件を変えて
H(n, r) = Σ(0 <= i <= stock[i]) H(n - 1, r-i) とすることで個数制限がある場合にも対応できる。
ただ動的計画法でH(n, r)の結果を再利用しても、ループを回す分計算量が増えてO(nr^2)になってしまう。
動的計画法(DP)で計算結果を再利用して計算量を減らす - sambaiz-net
ループの中身を分解すると
i = 0のとき:H(n - 1, r)i > 0のとき:H(n - 1, r - 1) + H(n - 1, r - 2) + ... + H(n - 1, r - stocks[i]) = H(n, r - 1) - H(n - 1, r - stocks[i] - 1)
となるので H(n, r) = H(n - 1, r) + H(n, r - 1) - H(n-1, r - 1 - stocks[i]) に変形すると計算量をO(nr)に落とすことができる。
class Stock
{
public:
Stock(vector<int> stocks);
int H(int r);
private:
vector<int> m_stocks;
map<pair<int, int>, int> records;
int H(int n, int r);
};
Stock::Stock(vector<int> stocks) { m_stocks = stocks; }
int Stock::H(int r)
{
return H(m_stocks.size(), r);
}
int Stock::H(int n, int r)
{
pair<int, int> key = {n, r};
if (records.count(key) != 0)
{
return records[key];
}
if (n <= 0 || r < 0)
{
records[key] = 0;
return 0;
}
if (r == 0)
{
records[key] = 1;
return 1;
}
if (n == 1)
{
if (m_stocks[n - 1] < r)
{
return 0;
}
return 1;
}
int h = H(n, r - 1) + H(n - 1, r) - H(n - 1, r - m_stocks[n - 1] - 1);
records[key] = h;
return h;
}