Pythonアルゴリズム072-1|ネットワーク線を切り取る

3649 ワード
アルゴリズム問題 パイ テキストリンク

72.ネットワーク線を切り取る


賢洙はネットの糸を1メートル2メートルに切りたいと思っている.
例えば、4 mのネットワーク線が与えられた場合
1) 1m+1m+1m+1m
2) 2m+1m+1m
3) 1m+2m+1m
4) 1m+1m+2m
5) 2m+2m
の5つの方法があります.(2)及び(3)及び(4)の場合、左側に対するせん断位置
違うと違う場合だと思います.
ネットワーク線の長さがnmの場合、いくつかのカット方法を考えることができますか?
■説明の入力
1行目はネットワーク線の全長,自然数N(3≦N≦45)である.
■出力説明
1行目の出力部に数列の最大長をインクリメントします.
■入力例1
7
■出力例1
21

『私の答え』


動的計画法についての説明を聞きました.

<解答>

  • f(n) = f(n-2) + f(n-1) 
    • 
코드를 입력하세요
n=int(input())
dy=[0]*(n+1)
dy[1] =1
dy[2]=2
for i in range(3,N+1) :
    dy[i]=dy[i-1]+dy[i-2]
print(dy[n])

    『反省点』


    『学んだこと』


    ソース:リンクテキスト

    どうてきけいかくほう


    :小部分入力問題を解決した後、この部分の問題の解を利用して大部分の問題を解決し、最終的に全体の問題を解決するアルゴリズム
    :上から下へのメソッドを使用して、最下位レベルの答えを取得した後にこれらの答えを保存し、その結果値を使用して親問題をジャンプします.
    =>

  • Memoization
    :プログラムを実行するときに以前に計算した値を保存し、再計算を回避することで、全体の実行速度を速める技術

  • 問題を分割する場合、一部の問題は繰り返し使用されます.
    (ex)フィボナッチ数列

    • 分割征服


    :問題をいくつかの部分に分けてから、問題が分けられないまでマージするアルゴリズムです.

  • 親から下へのメソッドの解

  • 通常は再帰関数を使用します

  • 問題を分割するとき、一部の問題は重複しません.
    (ex)マージソート、クイックソートなど

    • 異同


    (1)共通点
  • の問題を最小のユニット
    • に分割する.
    (2)差異

  • 動的計画:
    一部の問題は重複しており、親の問題を解決するために使用されます.
    アノテーション作成メソッドの使用(一部の問題の答えを保存して問題の最適化メソッドを回収)

  • 分割征服

  • 局所的な問題は繰り返してはいけない.

  • アノテーションが無効
    • Manacher's Algorithm
    AGグリッドドキュメントを使用して生産性を最大化