与えられたすべてのビットマスクの組み合わせを見つける方法i後続の値は "0"、jは "1"でもかまいませんか？

Question

入力。
私はビット配列nと2つの整数1<=i<=nと0<=j<=nを持っています。 iは、0であることができる後続の数字の最大値を示します。 jは、後続の数字の最大値を示します（1）。私はすべての可能なビット配列は、これらの制約を満たすnのサイズに返す方法を探し

所望の出力
。

すべての配列の組み合わせ（最初は制約なし）をループするだけで指数関数的な時間になります。 （特にi/j>>1の方が良いと思います）。 これらのビットマスクの組み合わせを効果的に見つける方法を教えてください。

例
入力：i = 1、j = 2、n = 3

結果：可能な配列は[0,1,0], [1,0,1],[1,1,0],[0,1,1]あります。

Answer 1

これはダイナミックプログラミングソリューションの優れた問題です。与えられた長さの与えられた数字（0または1）で始まる文字列の数を返すメソッドを持つだけで十分です。長nの桁数よりも0から始まり、メモ化1.

単純なPythonの溶液から始まる文字列の合計がある：

_c = {} # Cache 

def C(d, n, ij): 
    if n <= 1: 
     return 1 
    if (d, n) not in _c: 
     _c[(d, n)] = sum(C(1-d, n-x, ij) for x in xrange(1, min(ij[d], n)+1)) 
    return _c[(d, n)] 

def B(n, i, j): 
    ij = [i, j] # Easier to index 
    _c.clear() # Clears cache 
    return C(0, n, ij) + C(1, n, ij) 

print B(3, 1, 2) 
print B(300, 10, 20) 

結果は：

4 
1896835555769011113367758506440713303464223490691007178590554687025004528364990337945924158 

の値ので与えられた桁と長さは、反対の桁の値と長さが与えられた長さよりも小さいことに依存するが、解は長さによってますます値を計算することによっても得られる。 Pythonソリューション：

def D(n, i, j): 
    c0 = [1] # Initialize arrays 
    c1 = [1] 
    for x in xrange(1, n+1): # For each next digit calculate value 
     c0.append(sum(c1[x-y] for y in xrange(1, min(i, x)+1))) 
     c1.append(sum(c0[x-y] for y in xrange(1, min(j, x)+1))) 
    return c0[-1] + c1[-1] # Sum strings starting of length n with 0 and 1 

print D(3, 1, 2) 
print D(300, 10, 20) 

後でC++で実装する方が簡単です。