動的計画(DP)

4529 ワード
フィボナッチ どうてきけいかくほう テキストリンク
学習内容

  • 小さな問題を解決し、それを利用して大きな問題を解決し、最終的に問題全体を解決する戦略

  • 質問の答えを回収する方法

  • memorizationテクニック:小さな問題の値を格納し、大きな問題を解決する際にこれらの値を使用して、全体的な実行速度を速めます.

  • 代表的なのは,動的計画法でフィボナッチ数列を実現できることである.
    • インプリメンテーション
    フィボナッチ数列を実現
    復帰する
     // 피보나치 재귀 구현
    public int fibonacciFunc(int n) {
        if (n <= 1) {
            return n;
        }else {
            return fibonacciFunc(n - 1) + fibonacciFunc(n - 2);
        }
    }
    どうてきけいかくほう
    // 동적계획법, 재귀처럼 매번 계산하지 않고 메모이제이션을 통해 한 번 계산한 값은 저장 후 재사용
    public int dynamicFunc(int n) {
        Integer[] cache = new Integer[n + 1]; // 0이 포함되서 n + 1
        cache[0] = 0;
        cache[1] = 1;
        for (int i = 2; i < n + 1; i++) {
            cache[i] = cache[i-1] + cache[i-2];
        }
        return cache[n];
    }
    Selectors
    Spring式言語