2

私は単純なDP問題を解決しようとしています：

正の整数nが与えられると、次の3つのステップのいずれかを実行できます。1）それから1を引きます。
2）2で割り切れる場合は、2で割ります
。3）3で割り切れる場合は、3で割り
ます。nから1になる最小ステップ数を見つけて、ステップを印刷します。同じステップ数で目標を達成するための複数のソリューションがある場合は、これらすべてのソリューションを印刷してください。（難しい場合は、少なくともこれらの解決策の1つを印刷してください）。

最小ステップ数を取得することはそれほど難しくありません。次のようなボトムアップのDPソリューションを適用するだけです。

public int getMinSteps(int n) {
int[] dp = new int[n+1];

int i;
dp[1] = 0; 

for( i = 2 ; i < = n ; i ++ ) {
dp[i] = 1 + dp[i-1];
if(i%2==0) dp[i] = min( dp[i] , 1+ dp[i/2] );
if(i%3==0) dp[i] = min( dp[i] , 1+ dp[i/3] );
}
return dp[n];
}

しかし、プリントパス部分は解けませんでした。高レベルでは、最小値が決定されるすべてのレベルで「アクション」を停止する必要があると思いますか？

ここでいくつかの良い提案や解決策が得られることを願っています。

ありがとう！

4

2 に答える 2

3

最小パスを取得するのが最適な場合は、最適なステップを格納する別のフィールド、つまり-1、/ 2、または/ 3を取得します。おそらく、インジケーターとして1、を使用します。23

たとえば、、、を比較していa = 1 + dp[i-1]ます。が最小の場合、その数は-1にする必要があります。ステップをとして保存します。後で、フィールドにジャンプして、開始点、つまり1に到達するまで次のステップを見つけます。b = 1 + dp[i/2]c = 1 + dp[i/3]a1i-1

アップデート：

すべてのパスを印刷する場合は、すべての最適なステップを保存し、すべての組み合わせを印刷する必要があります。

詳細には、-1、/ 2、/ 3の3つのブールフィールドを使用して、最適なパスが特定の数を通過するかどうかを格納できます。その後、ツリーをトラバースするように、すべての組み合わせを再帰的に印刷できます。

int[] dp; // for minimum steps
bool[] gominus1;
bool[] godivideby2;
bool[] godivideby3;
List<Integer> steps;

PrintAllPath(int n) {
    if(n == 1) {
        // print steps
        return;
    }
    steps.push_back(n);
    if(gominus1[n]) {
        PrintAllPath(n - 1);
    }
    if(godivideby2[n]) {
        PrintAllPath(n / 2);
    }
    if(govidivideby3[n]) {
        PrintAllPath(n / 3);
    }
    steps.pop_back();
}
于 2012-11-19T04:44:39.937 に答える
1

パスを取得する方法は次のとおりです。

    public static int getMinSteps(int n) {
    int[] dp = new int[n + 1];
    String[] path = new String[n+1];
    int i;
    dp[1] = 0;
    path[1] = "end";

    for (i = 2; i <= n; i++) {
        dp[i] = 1 + dp[i - 1];
        if (i % 2 == 0) {

            if(dp[i] < 1 + dp[i/2]){
                path[i] = "sub 1," + path[i-1];
            }
            else {
               path[i] = "div by 2," + path[i/2];
            }

            dp[i] = min(dp[i], 1 + dp[i / 2]);

        }

        if (i % 3 == 0) {

             if(dp[i] < 1 + dp[i/3]){
                path[i] = "sub 1," + path[i-1];
            }
            else {
               path[i] = "div by 3," + path[i/3];
            }

            dp[i] = min(dp[i], 1 + dp[i / 3]);
        }

        if( i % 3 != 0 && i % 2 != 0) {
             path[i] = "sub 1," + path[i-1];
        }

    }
    System.out.println("number of steps = "+dp[n]+",path = "+path[n]);
    return dp[n];
}

これは、単一のパスを印刷するためのものです。すべてのパスを印刷するには、dp[i]への可能な限り最小限の方法をすべて追跡する必要があります。したがって、それらを格納するには、Stringの2次元配列が必要です。

于 2012-11-19T05:26:19.980 に答える