[Algorithm] Dynamic Programming

→重複演算を減らす.演算速度やメモリスペースを最大限に活用するデータの数も限られています.したがって,演算速度とメモリ空間を最大限に利用するための有効なアルゴリズムを制定する必要がある.

topdown\topdown

Boottom Upベンチマーク

上昇

Memoization

動的とは「プログラムの実行中」という意味です.プログラム実行中にプログラム実行に必要なメモリを割り当てる方法.
ex)フィボナッチ数列
an = an-1 + an-2, a1 = 1, a2 = 1
*プログラミングでは、これらの数列を配列またはリストとして表すことができます.数列自体がルールに従って並ぶ数なので.
フィボナッチ数列を再実現するコード

def fibo(x):
    if x == 1 or x == 2:
        return 1
    return fibo(x-1) + fibo(x-2)

print(fibo(4))

*質問
f(n)関数では,nが大きくなるにつれて再帰実行時間は幾何級数的に増加する.O(2^n)の時間的複雑度は時間的複雑度を計算することによって決定できる.

解決

このように,再帰関数を用いてフィボナッチ数列の点火式を確立できるが,単純な計算のたびに問題を効果的に解決することはできない.これらの問題はダイナミック図面で解決できます.

の大きな問題を小さな問題に分けることができます.

小問題から求めた答えは,それを含む大問題においても同様である.

注釈
動的プログラミングを実現する方法の1つは,求めた結果をメモリ空間に記録し,同じ式を再び呼び出して,記録した結果を直接得る方法である.注記は現在、値を格納する方法であるため、キャッシュとも呼ばれます.
ダイナミックプログラミングは大きな問題を小さな問題に分け,同じ問題であれば1回の問題を解くだけで効果的に問題を解決できるアルゴリズムテクニックである.実際,高速ソートでは大きな問題を小さな問題に分ける方法も紹介されている.クイックソートでは、ソートを実行するときにソートするリストを分割し、全体的なソートにすることができます.これは分割征服アルゴリズムに分類される.
再帰関数ではなく繰り返し文を使用して、オーバーヘッドを削減できます.
再帰関数を用いて動的プログラミングソースコードを記述する方法で,大きな問題を解決するために小さな問題を呼び出すことをtopdown方式と呼ぶ.
逆に、小さい頃から問題から順番に答えが出てきたということから、一時停止方式と呼ばれています.

タワー

→注釈式、方式は下向き式、基準上昇式は上向き式とも呼ばれる.ダイナミックプログラミングの典型的な形式はゲート方式です.「ベースライン」方式で使用した結果格納リストを「DPテーブル」と呼び、「コメント」は現在「タワー」方式のみで使用されている表現となっている.
数列は配列またはリストとして表すことができ、注釈は写真(DICT)データ型などの異なるデータ型を異なる時間に使用することができるようになった.場合によっては、必要なのはすべてのa-1の前の数列ではなく、anです.この場合は事前資料型の方が有効です.

1として作成

整数Xが与えられた場合、整数Xに使用できる演算は4つあります.

Xを5で割って5で割った.

Xを3で割って3で割った.

Xを2で割って2で割った.

Xから1を減算します.

# 못품 / 수열 식을 세워라잉..
x = int(input())

d = [0] * 30001

# i가 x와 동일하듯이 작동한다.
for i in range(2, x+1):
    d[i] = d[i-1] + 1
    if i % 2 == 0:
        d[i] = min(d[i], d[i // 2]+1)
    if i % 3 == 0:
        d[i] = min(d[i], d[i // 3]+1)
    if i % 5 == 0:
        d[i] = min(d[i], d[i // 5]+1)
print(d[x])

ゆかこうじ

長方形の薄い土地があり、長いn、長い2があります.タイは1 x 2,2 x 1,2 x 2の蓋でこの薄い床を埋めたいと思っています.

# 바닥 공사 품
n = int(input())

d = [0] * 1001
d[1] = 1
d[2] = 3

for i in range(3, n+1):
    # 2x1은 마지막에 하나 올 수 있고 앞에 길이가 i-1 그외에 나머지 두개는 모두 i-2에다가 붙임
    d[i] = (d[i-1] + d[i-2]*2)%796796
    
print(d[n])