[アルゴリズム]動的プログラミング

4273 ワード
Algorithms テキストリンク
ダイナミックプログラミング
  • メモリを使用して、実行時間の効率を迅速に向上させる方法
  • 計算された結果(小さな問題)は、
    • の再計算を回避するために、独立したメモリ領域に格納される.
  • 動的プログラミングの実施は、通常、2つの方法で構成される.
    DP条件

  • さいてききょくぶこうぞう
    :大きな問題は小さな問題に分けることができ、小さな問題の答えは集中して大きな問題を解決することができる.

  • 問題の重複
    :同じ小さな問題を繰り返し解決
    • フィボナッチ数列
    public class Fibo {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        System.out.println(fibo(n));
    }
    public static int fibo(int idx) {
        if (idx < 0) {
            return 0;
        } else if (idx < 3) {
            return 1;
        } else {
            return fibo(idx-1) + fibo(idx-2);
        }
    }
}
  • 再配置時に「重複部分の問題」が発生
    Ex.fibo(5)を取得する場合は、次の手順に従います.
    fibo(5) = fibo(4) + fibo(3)
    fibo(4) = fibo(3) + fibo(2)
    fibo(3) = fibo(2) + fibo(1)
    fibo(3) = fibo(2) + fibo(1)
    ...
  • fibo(3)、fibo(2)、fibo(1)の繰り返し計算
    Memoization
  • 注記現在はDPを実施する方法の1つである->上から下へ
  • メモリ領域で最も安価な結果を記録する
    • レコード
  • 値、キャッシュとも呼ばれる
    フィボナッチ数列-DP利用
    public class FiboWithDP {
    public static int[] d = new int[100];
    public static void main(String[] args) {
        System.out.println(f(99));
    }
    public static int f(int x) {
        if (x==1 || x==2) {
            return 1;
        }
        if (d[x] != 0) {
            return d[x];
        } else {
            d[x] = f(x-1) + f(x-2);
            return d[x];
        }
    }
}
    質問1:アリファイター
  • アリ戦士は不足した食糧を補充するためにバッタ村の食糧倉庫を襲撃する準備をしている.
    バッタ村には複数の穀倉があり、穀倉は直線で構成された
    • である.
  • 各穀倉には一定数の食糧が貯蔵されており、アリ戦士は選択的に穀倉を略奪し、食糧を奪う.
    このときバッタ偵察兵たちは一直線上に存在する穀倉の中で、隣接する穀倉が攻撃を受けると、すぐに発見される.
    • そのため、アリ戦士は偵察兵に発見されないように、食糧倉庫を略奪し、少なくとも1つ以上の食糧倉庫を略奪しなければならない.
  • アリ戦士のためにN個の食糧倉庫に関する情報を入手する場合は、食糧の最低価格を取得してください.
    [入力]
    4
    1 3 1 5
    [出力]
    8
    • に答える
    質問2:1
  • の整数Xが与えられた場合、整数Xに使用できる演算は4つある.
  • Xを5で割って5で割った.
  • Xを3で割って3で割った.
  • Xを2で割って2で割った.
  • Xから1を減算します.
  • の整数Xが与えられる場合、4つの演算を適宜用いて値を1とすることが望ましい.
    使用演算回数の最大値を出力してください.
    • 例えば
  • 、26であれば3回の演算の最大値を算出する.
    26 -> 25 -> 5 -> 1
    [入力]
    26
    [出力]
    3
    • に答える
    質問3:効率的な通貨構成
  • Nの通貨があります.これらの通貨の個数を最小限に抑え、その価値の和をM元にしようとした.
    このとき、各通貨はいくつか使えます.
    • 例えば
  • 、2元、3元単位の通貨がある場合、15元を作るために5つの3元を使うのが最小の通貨数です.
    • 最低通貨数を出力して
  • M元
    • を作成するプログラムを作成します.
  • 不可能時出力-1.
    [入力]
    2 15
    2
    3
    [出力]
    5
    • に答える
    問題4:金鉱
  • nメートルの大きさの金鉱があります.金鉱は1格に分けられ、各格には特定の大きさの金がある.
  • 採掘者は第1列から金を洗い始めた.最初は最初の列のどの行からでも出発できます.
    その後m−1回経過し,右上,右下,右下の3つの位置のいずれかに移動する.
  • の結果に基づいて、プログラムを作成し、採掘者が得ることができる最大の黄金サイズを出力する.
    • 第
  • 行判例数:T入力
  • 各試験盤盤第1行n及びm入力
  • 第2行入力n*mに埋蔵された金の数
    [入力]
    2
    3 4
    1 3 3 2 2 1 4 1 0 6 4 7
    4 4
    1 3 1 5 2 2 4 1 5 0 2 3 0 6 1 2
    [出力]
    19
    16
    • に答える
    質問5:兵士の配置
  • N人の兵士をランダムにリストした.どの兵士にも一定の戦闘力がある.
  • 兵士を配置する場合は、戦闘力の高い兵士が前に来るように降順に配置しなければならない.
    言い換えれば、前の兵士の戦闘力は後ろの兵士より高い.
  • はまた、配置中に特定の位置にある兵士を排除する方法を使用した.同時に残りの兵士の数を最大にしなければならない.
    [入力]
    7
    15 11 4 8 5 2 4
    [出力]
    2
    • に答える
    出典:これは就職のためのコードテストです.羅東彬
    Androidの抽象クラスとインタフェースの実践
    Flaskはログインと登録を行います(mysql、sessionと2つのフックbefore_requestとcontext_processor)