ダイナミックプログラミングソリューションの説明

Question

これは問題です。レンガの数nが3〜200の場合、ビルド可能な階段の数を返します。階段の各タイプは2つ以上の階段で構成する必要があります。同じ高さに2つのステップがあることは許されません - 各ステップは以前のものよりも低くなければなりません。すべてのステップには、少なくとも1つのレンガを含める必要があります。ステップの高さは、そのステップを構成するレンガの総量として分類されます。

たとえば、N = 3の場合、階段を作成する方法は1つしかありません。最初のステップの高さは2、次のステップの高さは1です。（＃はレンガを示します）

# 
## 
21 

N = 4、あなたはまだのみ1段の階段の選択肢がある場合：

# 
# 
## 
31 

しかし、N = 5を、あなたが与えられたレンガの階段を構築することができる2つの方法があります。 2段の階段は高持つことができます（4、1）または（3、2）、以下に示すよう：

# 
# 
# 
## 
41 

# 
## 
## 
32 

を私はオンライン解決策を見つけたが、私は非常に直感的に動的なプログラミングソリューションを理解していません。

public class Answer { 

    static int[][] p = new int[201][201]; 

    public static void fillP() { 
     p[1][1] = 1; 
     p[2][2] = 1; 

     for (int w = 3; w < 201 ; w++) { 
      for (int m = 1; m <= w; m++) { 
       if (w-m == 0) { 

        p[w][m] = 1 + p[w][m-1]; 

       } else if (w-m < m) { 

        p[w][m] = p[w-m][w-m] + p[w][m-1]; 

       } else if (w-m == m) { 
        p[w][m] = p[m][m-1] + p[w][m-1]; 

       } else if (w-m >m) { 

        p[w][m] = p[w-m][m-1] + p[w][m-1]; 
       } 

      } 
     } 
    } 

    public static int answer(int n) { 

     fillP(); 
     return p[n][n] - 1; 

    } 

} 

特に、配列内の連続した各エントリ間の関係はどのようになりますか？

Answer 1

これは非常に興味深い質問です。まずは、recurrence relationを理解してみましょう：

我々は現在、高さhのステップを構築し、私たちが使用して左bレンガを持っている場合は、私たちはここから階段を完了でき、いくつかの方法が全ての和に等しいです階段を高さh'とb - h'レンガの次のステップで完了させる方法は、0 < h' < hです。

このような漸化関係が成立すると、再帰的な解を考案することができます。しかし、現在の状態では、解は指数関数的に実行されます。そこで、我々は単に「キャッシュ」我々の結果を行う必要があります。

import java.util.Scanner; 

public class Stairs { 
    static int LIMIT = 200; 
    static int DIRTY = -1; 
    static int[][] cache = new int[LIMIT + 2][LIMIT + 2]; 

    public static void clearCache() { 
    for (int i = 0; i <= LIMIT + 1; i++) { 
     for (int j = 0; j <= LIMIT + 1; j++) { 
     // mark cache as dirty/garbage values 
     cache[i][j] = DIRTY; 
     } 
    } 
    } 

    public static int numberOfStaircases(int level, int bricks, int steps) { 
    // base cases 
    if (bricks < 0) return 0; 
    if (bricks == 0 && steps >= 2) return 1; 

    // only compute answer if we haven't already 
    if (cache[level][bricks] == DIRTY) { 
     int ways = 0; 
     for (int nextLevel = level - 1; nextLevel > 0; nextLevel--) { 
     ways += numberOfStaircases(nextLevel, bricks - nextLevel, steps + 1); 
     } 
     cache[level][bricks] = ways; 
    } 

    return cache[level][bricks]; 
    } 

    public static int answer(int n) { 
    clearCache(); 
    return numberOfStaircases(n + 1, n, 0); 
    } 

    public static void main(String[] args) { 
    Scanner scanner = new Scanner(System.in); 
    int n = scanner.nextInt(); 
    System.out.println(answer(n)); 
    } 
} 

あなたが提供されているコードから、著者は一歩さらに行って、純粋に反復バージョンで再帰的なソリューションを置き換えるかのように、それはそうです。つまり、作者はbottom-up solution rather than a top-down solutionです。

我々はまた、より多くの数学的問題にアプローチできます。n = 6ためだから、

How many distinct non-trivial integer partitions does n have?

を、我々は持っている：5 + 1、4 + 2、3 + 2 + 1を。だからanswer(6) = 3。面白いことに、Euler provedは、与えられたnのための別個の整数パーティションの数は、必ずしも別個の奇数の整数パーティションの数と常に同じではないということです。

（この質問がどこから来ているか分かります）