1

私は動的計画法のメモ化を学ぼうとしていて、それに沿ってフォローしようとしているMITからYouTubeでビデオを見ていました。N番目の値を配列と比較する方法がわかりません。

int[] memo;
public int fib(int n) {
    int f = 0;

    if n is in memo then return memo[n] <----not sure how to code this line.

    if (n<=2) {
        f = 1;
    } else {
        f = fib(n-1) + fib(n-2);
    }

    memo[n] = f;
    return f;
}
4

5 に答える 5

2

でそれを行うArrayList：

ArrayList<Integer> memo = new ArrayList<Integer>();

public int fib(int n) {
    if (memo.size() == 0)
       memo.add(0); // element 0 is never accessed
    return fib2(n);
}

private int fib2(int n) {
    int f = 0;

    if (n < memo.size())
       return memo.get(n);

    if (n<=2) {
        f = 1;
    } else {
       f = fib2(n-2) + fib2(n-1);
    }

    memo.add(f); // elements inserted in order
    return f;
}

配列でそれを行う：

int[] memo;

public int fib(int n) {
    memo = new int[n+1]; // all initialized to 0
    return fib2(n);
}

private int fib2(int n) {
    int f = 0;

    if (memo[n] != 0)
       return memo[n];

    if (n <= 2) {
        f = 1;
    } else {
        f = fib2(n-2) + fib2(n-1);
    }

    memo[n] = f;
    return f;
}
于 2013-02-17T13:08:35.347 に答える
1

アルゴリズムが配列に挿入されることはないため、値を使用してmemo配列を初期化できます。-1-1

したがって、memo[i]すでに挿入されているかどうかを確認するということは、を確認する必要があることを意味しますmemo[i] != -1。

注意：この概念は実際にはメモ化と呼ばれています

于 2013-02-17T12:59:35.437 に答える
0

配列を単一の要素と比較することはできません。

おそらく必要なのは、計算されていない値に対して-1のダミー値があると仮定することです。

if (memo[n] != -1) return memo[n]

于 2013-02-17T12:58:13.617 に答える
0

私はJava用のHashMapを使用するのが好きです。私の経験から、HashMapを使用するとメモ化を非常に簡単に実装できます。https://docs.oracle.com/javase/7/docs/api/java/util/HashMap.html

4つのステップ：

  1. ベースケースを取得する

  2. m.get(n) == nullサブ問題が計算されたかどうかを確認するために使用します。

  3. （2）が真でない場合は、再帰的に計算してHashMapに保存します。

    HashMapのキーは、現在のサブ問題識別子です（フィボナッチの場合、n番目のフィボナッチシーケンスのnです。値は、未解決の問題を解決する再帰呼び出しです。

  4. （2）が真の場合、m.get（n）を返します。

4つのステップを使用したフィボナッチの例を次に示します。

HashMap<Integer, Integer> memo = new HashMap<Integer,Integer>();

int fib(int n) {

    //1. base case
    if (n <= 1) 
        return n; 

    //2. check if sub problem is computed yet.
    if (m.get(n) == null) {

        //3. if not, compute the sub problem.
        m.put(n, fib(n - 1) + fib(n - 2));
    }

    //4. if so, return the result. 
    return m.get(n); 
}

多くのメモ化の問題についても、まったく同じアプローチをとることができます。

于 2016-01-20T14:23:38.563 に答える
0

奇妙なことに、この質問には0の賛成票がありますが、4つの回答があり、どれも本当に満足のいくものではありません。これは、4つの異なる方法を使用してそれらを比較する実装とテストの例です。

import java.util.ArrayList;
import java.util.HashMap;

public class Fib {

    // Straightforward implementation:
    public static int fib(int n) {
    if (n <= 1) {
        return n;
    }
    return fib(n - 1) + fib(n - 2);
    }

    // Using array:
    static int[] memoArray;
    public static int fibArray(int n) {
    memoArray = new int[n];
    return fibArrayHelper(n);
    }
    private static int fibArrayHelper(int n) {
    if (n <= 1) {
        return n;
    } else {
        if (memoArray[n - 2] != 0) {
        return memoArray[n - 2];
        }
        memoArray[n - 2] = fibArrayHelper(n - 2) + fibArrayHelper(n - 1);
        return memoArray[n - 2];
    }
    }

    // Using ArrayList:
    static ArrayList < Integer > memoArrayList = new ArrayList < Integer > ();

    public static int fibArrayList(int n) {
    return fibArrayListHelper(n);
    }

    private static int fibArrayListHelper(int n) {
    if (n <= 1) {
        return n;
    } else {
        if (n - 2 < memoArrayList.size())
        return memoArrayList.get(n - 2);
        else {
        memoArrayList.add(fibArrayListHelper(n - 2) + fibArrayListHelper(n - 1));
        return memoArrayList.get(n - 2);
        }
    }
    }

    // Using HashMap:
    static HashMap < Integer, Integer > memoHash = new HashMap < Integer, Integer > ();

    static public int fibHashMap(int n) {
    if (n <= 1)
        return n;
    if (memoHash.get(n) == null) {
        memoHash.put(n - 2, fibHashMap(n - 1) + fibHashMap(n - 2));
    }
    return memoHash.get(n - 2);
    }


    public static void main(String args[]) {
    long preTime, postTime;
    int x = 35;

    preTime = System.nanoTime();
    System.out.printf("%17s: %d", "fib(" + x + ")", fib(x));
    postTime = System.nanoTime();
    System.out.printf(", computed in %10d nanoseconds.\n", postTime - preTime);

    preTime = System.nanoTime();
    System.out.printf("%17s: %d", "fibArray(" + x + ")", fibArray(x));
    postTime = System.nanoTime();
    System.out.printf(", computed in %10d nanoseconds.\n", postTime - preTime);

    preTime = System.nanoTime();
    System.out.printf("%17s: %d", "fibArrayList(" + x + ")", fibArrayList(x));
    postTime = System.nanoTime();
    System.out.printf(", computed in %10d nanoseconds.\n", postTime - preTime);

    preTime = System.nanoTime();
    System.out.printf("%17s: %d", "fibHashMap(" + x + ")", fibHashMap(x));
    postTime = System.nanoTime();
    System.out.printf(", computed in %10d nanoseconds.\n", postTime - preTime);
    }
}
于 2017-02-02T05:25:44.530 に答える