動的計画法 - okinawa

まだ、初歩的な部分に触れただけなので追記したい。

動的計画法とは
自分の理解
例題
例題の解答コード
参考サイト

動的計画法とは

動的計画法（どうてきけいかくほう、英: Dynamic Programming, DP）は、計算機科学の分野において、アルゴリズムの分類の1つである。対象となる問題を複数の部分問題に分割し、部分問題の計算結果を記録しながら解いていく手法を総称してこう呼ぶ。

細かくアルゴリズムが定義されているわけではなく、下記2条件を満たすアルゴリズムの総称である。

1、帰納的な関係の利用：より小さな問題例の解や計算結果を帰納的な関係を利用してより大きな問題例を解くのに使用する。
2、計算結果の記録：小さな問題例、計算結果から記録し、同じ計算を何度も行うことを避ける。帰納的な関係での参照を効率よく行うために、計算結果は整数、文字やその組みなどを見出しにして管理される。

動的計画法 - Wikipedia

自分の理解

現在地に至るまでの１個手前の選択肢を全部考える。

再帰関数と考え方が似ている気がする。

実際、フィボナッチ数列を動的計画法で作れるようです。

N=10
memo=[0]*N

def fib(N):
  if N <= 1:
    return 1
  else:
    # メモされていなければ計算
    if memo[N] == 0:
      memo[N] = fib(N-1) + fib(N-2)
    else:
      return memo[N]#メモ済みであれば、メモを返す

例題

初めて触れた動的計画法で解く問題。
わかりやすいコードで解ける、教育的で良い問題だと思った。
atcoder.jp

例題の解答コード

n,k=map(int,input().split())
a=list(map(int,input().split()))
b=list(map(int,input().split()))

dp=[[False]*n for _ in range(2)]

dp[0][0]=True
dp[1][0]=True

for i in range(1,n):
    #a[i-1]がTrueなら、a[i]へいけるか、b[i]へ行けるかを考える
    if dp[0][i-1]:
        #a[i-1]からa[i]へいけるか？
        if abs(a[i-1] - a[i]) <= k:
            dp[0][i] = True
        #a[i-1]からb[i]へいけるか？
        if abs(a[i-1] - b[i]) <= k:
            dp[1][i] = True

    #b[i-1]がTrueなら、a[i]へいけるか、b[i]へ行けるかを考える
    if dp[1][i-1]:
        #b[i-1]からa[i]へいけるか？
        if abs(b[i-1] - a[i]) <= k:
            dp[0][i] = True
        #b[i-1]からb[i]へいけるか？
        if abs(b[i-1] - b[i]) <= k:
            dp[1][i] = True



if dp[0][n-1] or dp[1][n-1]:
    print("Yes")
else:
    print("No")