ネットワーク線のクリップ

2966 ワード
python アルゴリズム#アルゴリズム# テキストリンク
作成日:2022年2月22日午後2:39

インプリメンテーションコード

# 네트워크 선 자르기 (Bottom-Up)
import sys
sys.stdin = open("input.txt", "rt")

n = int(input())
dy = [0]*(n+1)

dy[1] = 1
dy[2] = 2

for i in range(3, n+1):
    dy[i] = dy[i-2] + dy[i-1]

print(dy[n])

どうてきけいかくほう


この問題はダイナミックプランニング法で簡単に解決できる.「
  • 動的計画法」は、問題を非常に直感的な答えに分解し、ルールを見つけて、より広い範囲に広がる問題を解決する技術です.
  • 点火式
  • という問題では,直線の長さが1の場合,1種(1 m 1個),2の場合,2種(1+1,2)が直感的に見られる.
  • 線の長さが3の場合、線の長さが1の場合、線の長さが2の場合と同じ数が発生します.
  • すなわちf(n)=f(n−2)+f(n−1)が成立する.
  • では、初期値1と2を配列に格納し、ループ文で値を大きくしたときの答えを検索できます.
    • 階段を上る
    ピザ出前距離(DFS)