6

男性が n 段の階段を駆け上がっており、一度に 1 段、2 段、または 3 段進むことができます。次に、子供が階段を上る方法の数を数えるプログラムを作成します。

与えられたコードは以下のようなものです

public static int countDP(int n, int[] map) {
 if (n<0)
   return 0;
 else if (n==0)
   return 1;
 else if (map[n]>-1)
   return map[n];
 else {
    map[n] = countDP(n-1, map) + countDP(n-2, map) + countDP(n-3, map);
    return map[n]; }
 }

Java ではなく、C と C++ を知っています。これは Cracking the Coding のインタビュー本からのものです。誰でも説明できますか

  1. 彼女がここで関数マップを使用する理由と方法は? ここのマップは配列ですよね？

  2. 入力をマップ配列に保存する行が表示されませんが、どのように何かを返すのでしょうか?

  3. 誰でもこのコードの C++ または C バージョンのアイデアを持っていますか? このコードを理解するのは難しいです。おそらくJAVAの文法によるものではなく、動的プログラミングの暗黙の構造によるものです。

  4. このアルゴリズムの時間計算量はどれくらいになるでしょうか? O(3^n) よりも小さい必要がありますか?

大変ありがたく存じます。

みんなありがとう

4

5 に答える 5

14

さて、これがコードが行うことです。

 `if (n<0)`
    `return 0;`

十分なステップが残っていない場合は、カウントしないでください。たとえば、あと 2 ステップあるが、ユーザーが 3 つのステップを実行しようとしている場合、それは可能な組み合わせとしてカウントされません。

else if (n==0) return 1;

残りのステップ数が、ユーザーが実行しようとしている使用可能なステップ数と一致する場合、それは可能な組み合わせです。したがって、これは可能な組み合わせであり、有効な組み合わせの総数に追加する必要があるため、1 を返します。

else if (map[n]>-1) return map[n];

これが動的計画法の部分です。配列内のすべての値の値が -1 であると仮定します。したがって、数値が -1 より大きい場合は、既に解決されているため、解決する代わりに、ステップ番号 n からの組み合わせの総数を返します。

`map[n] = countDP(n-1, map) + countDP(n-2, map) + countDP(n-3, map);`

return map[n]; }

最後に、この部分でコードを解決します。可能な組み合わせの数は、ユーザーが 1 ステップ実行した場合に取得できる可能な組み合わせの数 + ユーザーが 2 ステップ実行した場合に取得できる可能な組み合わせの数 + ユーザーが実行した場合に取得できる可能な組み合わせの数に等しい3 つのステップ。

例として、5 つのステップがあるとします。

簡単な実行は次のようになります。

//The number of solutions from the fifth step

countDp(5) = countDp(4)+countDp(3)+countDp(2);

//Number of solutions from the fourth step

countDP(4) = countDp(3)+countDp(2)+countDp(1);

//Number of solutions from the third step

countDp(3) = countDp(2)+countDp(1)+countDp(0);
//Number of solutions from the second step
countDp(2) = countDp(1)+countDp(0)+countDp(-1);
//Number of solutions from the first step
countDp(1) = countDp(0) + countDp(-1)+countDp(-2);
//Finally, base case
countDp(0) = 1;

countDp(-1)= 0;
countDp(-2)= 0;
countDp(1) = 1+0+0 = 1;
countDp(2) = 1+1+0 = 2;  //Dynamic programming: did not have to resolve for countDp(1), instead looked up the value in map[1]
countDp(3) = 2+1+1 = 4;  //Dynamic programming, did not have to solve for countDp(1), countDp(2), instead looked up value in map[1] and map[2]
countDp(4) = 4+2+1=7 //Dynamic programming, did not have to solve for CountDp(3),CountDp(2), CountDp(1), just looked them up in map[3],map[2],map[1]
countDp(5)=  2+4+7=13 //Dynamic programming, just used map[4]+map[3]+map[2]
于 2013-07-22T03:24:34.587 に答える
3

彼女がここで関数マップを使用する理由と方法は?

この本は、memoizationと呼ばれる動的プログラミング手法を示しています。同じ数値の再計算を避けるために使用されます。要素が でない場合、-1再計算されており、再計算は多くの CPU サイクルを浪費することを意味します。DP は値を 1 回計算し、値が必要になるたびにそれを返します。

ここのマップは配列ですよね？

正しい、map配列型です。

入力をマップ配列に保存する行が表示されませんが、どのように何かを返すのでしょうか?

これは、下から 3 行目の割り当てになります。

map[n] = countDP(n-1, map) + countDP(n-2, map) + countDP(n-3, map);

誰でもこのコードの C++ または C バージョンのアイデアを持っていますか? このコードを理解するのは難しいです。おそらくJAVAの文法によるものではなく、動的プログラミングの暗黙の構造によるものです。

そうです、DPとメモ化は慣れるまでに時間がかかります。紙と鉛筆でこのアルゴリズムを 1 回実行して、小さな数、たとえば 10 を求めます。これは、答えの最適な部分構造が、このアルゴリズムが答えを非常に迅速に導き出すのにどのように役立つかを示しています。

このアルゴリズムの時間計算量はどれくらいになるでしょうか? O(3^n) よりも小さい必要がありますか?

絶対！各項目は正確に 1 回計算され、各項目は計算に償却がかかるO(1)ため、このコードの全体的な複雑さは ですO(N)。countDP(K)これは、計算するための再帰呼び出しのチェーンが再帰呼び出しをどのように受け取るかを観察すると、直感に反する可能性がありO(K)ます。Kただし、各呼び出しはのアイテムの計算を終了します(が一方通行であることにmap注意してください: セルに負でない値を設定すると、それは永久に負でないままになるため、同じ値を再計算してmap他の呼び出しパスでも同じO(1)時間がかかります。

于 2013-07-22T03:17:07.323 に答える
0

1.) map は整数配列です。Java の表記法では、map[n] はインデックス n の整数値を返します。

2.) map[n] はインデックス n の整数値を返すため、戻り値は整数です。値が配列に保存されるのは 

map[n] = countDP(n-1, map) + countDP(n-2, map) + countDP(n-3, map);

これは、可能なすべての 1 、 2 、および 3 の組み合わせを数えることによってステップの合計を見つけるための再帰呼び出しです。

3.)

int countDP(int n, int map[])
{
if (n<0)
    return 0;
else if (n==0)
    return 1;
else if (map[n]>-1)
    return map[n];
else {
    map[n] = countDP(n-1, map) + countDP(n-2, map) + countDP(n-3, map);
    return map[n]; 
}


}

4.) はい、複雑さは O(3^n) よりもはるかに高速です。

于 2013-07-22T03:22:17.960 に答える
0 
/**
 * Created by mona on 3/3/16.
 */
import java.util.Hashtable;
public class StairCount {
    /*
     A man is running up a staircase with n steps, and can go either 1 steps, 2 steps,
      or 3 steps at a time. count how many possible ways the child can run the stairs.
     */
    static Hashtable<Integer, Long> ht=new Hashtable<>();

    public static long stairs(int n){
        if (!ht.containsKey(1)){
            ht.put(1, (long) 1);
        }
        if (!ht.containsKey(2)){
            ht.put(2, (long) 2);
        }
        if (!ht.containsKey(3)){
            ht.put(3, (long) 4);
        }

/*
        if (!ht.containsKey(n)){
            ht.put(n, stairs(n-1)+ht.get(1)+stairs(n-2)+ht.get(2)+stairs(n-3)+ht.get(3));
        }
*/
        if (!ht.containsKey(n)){
            ht.put(n, stairs(n-1)+stairs(n-2)+stairs(n-3));
        }
        return ht.get(n);
    }
    public static void main(String[] args){
        System.out.println(stairs(4));

    }
}

// 4 の答えは 14 で、5 の答えは 27 です。私の思考プロセスが間違っていた理由を誰かコメントできますか?

于 2016-03-04T05:28:52.497 に答える