こんばんは(;´･ω･)

前回、ここで最後に DP に触れてみましたが、
今一ピンと来なかったので、もうちょっとカジってみます(*´з`)９

初心者なので、早速ググってみると
"分からない"、
"壁"、
"登竜門"　
とか色々、一緒に出てきました。
やっぱり皆、一度はハマるんですね。

取りあえず、やってみましょう。
初級問題:与えられた要素を任意に組み合わせて最大値を求めてみます。

Combination_DP.py

N = 3 # 要素数
A = [7,-6,9] #要素

memo = [0]*(N+1) # 要素数 + 1 のメモを 1 行(all 0)を用意

for i in range(N):
    memo[i+1]=max(memo[i],memo[i]+A[i])

print(memo[N])#回答の表示

for 文は何をしているのでしょうか？
一個ずつ追って見ましょう。

i = 0 のとき
memo[0] には 0 が格納されていますが、
memo[0] + A[0] = 0 + 7 と比べると何方が大きいでしょうか？
勿論、後者ですよね。
計算結果は memo[1] に 7 を格納します。

i = 1 のとき
memo[1] にある 7 と
memo[1]+A[1] の 1 とでは、どちらが大きいでしょうか？
前者ですよね？
この結果は memo[2] に格納します。

i = 2 のとき
memo[2] にある 7 と
memo[2] + A[2] の 16 はどちらが大きいですか？
はい、結果を格納します。

最後に memo[3] を表示すれば回答にたどり着けます。
御覧の通り、計算結果を次のセルに渡すので、最終的には
計算したい要素数 + 1 のメモが必要です。
個人的には、以下のような書き方もあると思います。

Combination_DP.py

N = 3
A = [7,-6,9]

memo = [0]*(N)
memo[0] = A[0] 

for i in range(1,N,1):
    memo[i]=max(memo[i-1],memo[i-1]+A[i])

print(memo[N-1])

上記は memo[0] に初期値を入れて、
for 文をmemo[1]から始めています。
こうすることで、ひとつ前の値(= i-1)を参考に、
今の値(= i ) を算出することが出来ます。

へー( ﾟДﾟ)
っとなったところでググって次なる問題を探した所、
こちらに出会いました。
分かり易くて感謝のコメントを思わず捧げてしまいました。

早速、カエル問題にチャレンジしました。

min_cost.py

a = [2,9,4,5,1,6,10]
N = len(a)

memo = [0]*(N)

for i in range(1,N,1):
    memo[i]=memo[i-1]+abs(a[i-1]-a[i])
    if i > 1 :
        memo[i] = min(memo[i],memo[i-2]+abs(a[i-2]-a[i]))

print(memo[N-1])

有識者の皆様は初期化する意味で、INF を全セルに代入し、
+1 で移動するときのコストと比較して小さい方を上書き。
そのあとに +2 で移動するときのコストを比較して、
小さければ上書きし最終セルを出力されています。

個人的には、All 0 初期値とし、
+1 のコストをいきなり上書きしても問題ないと思います。
なぜなら、最初に必ず+1 で移動した場合のコストを埋めてから、
+2 の移動コストと比較しないと問題が解けないからです(笑)
もう一つの書き方も試しました。

Combination_DP.py

a = [2,9,4,5,1,6,10]
N = len(a)

memo = [0]*(N)

for i in range(N-1):
    memo[i+1]=memo[i]+abs(a[i+1]-a[i])
    if i >= 1 :
        memo[i+1] = min(memo[i+1],memo[i-1]+abs(a[i+1]-a[i-1]))

print(memo[N-1])

私は冒頭にあるメモの概念と、
以下のアプローチをイメージ出来たら理解した気分になれました(笑)

Step 1. +1 のコストを最初に memo
Step 2. +2 のコストと Step 1 で求めた memo を比較して小さい方の値を上書き

まだまだ、足を踏み入れたばかりなので、
もう少し違う問題も挑戦しようと思います。

11/26 update
例えば、+1 , +2 でカエルが跳んだ場合の MIN コストを求めていましたが、
飛ばす柱の数を K と定義されたらどうしますか？
問題によりますが、K まで 1 ずつインクリメントして
全てのケースを比較して、MIN コストを求めるとすると、どうでしょう。
例として 1 飛ばしと 2 飛ばしを書いてみました。

Combination_DP.py

K = [1,2]
a = [2,9,4,5,1,6,10]
N = len(a)

memo = [0] * (N)

for i in range(1,N,1):
    memo[i] = memo[i-1]+abs(a[i]-a[i-1])
    for k in K:
        if i > k:
            memo[i] = min(memo[i],memo[i-(k+1)]+abs(a[i]-a[i-(k+1)]))
    
print(memo[N])

各ポイントに着地するときに、隣にジャンプ or +1 or +2 を三択して
最小値を求めてから次に向かうことで Goal に辿り着くときには最小値を求められる算段です。
下の図は、プログラムが最小を選びながら進んでいるイメージをまとめたものです。
もっと分かり易くできると思うんですけど、すいません、センスがない m(_ _)m

配る DP 行きましょう。

Combination_DP.py

K = [1,2]
a = [2,9,4,5,1,6,10]
N = len(a)

memo = [0] * (N)

for i in range(N-1):
    memo[i+1] = memo[i]+abs(a[i+1]-a[i])
    for k in K:
        if i >= k:
            memo[i+1] = min(memo[i+1],memo[i-k]+abs(a[i+1]-a[i-k]))

print(memo[N-1])

DP の事だけ考えると、
他のこと忘れますね(笑)

11/27 update
昨日のイメージをもう少し補足してみます。
memo[0],memo[1]までは良いと思いますが、memo[2]からが本番です。

最小値 2 を探し出しました。
次の memo[3] は memo[0] - memo[2] の 3 つ中から最適値を見つけます。

残りの作業は同じ内容なので補足説明は省きます。

行ってみたいなー、幸福の国。。
っというわけで、以下の問題にも挑戦しました。
勿論、問題はここを参照にしています

---------------------------------------------------------------------------
N 日間の夏休みです。i 日目には、

A: 海で泳ぐ。幸福度 ai を加算
B: 山で虫取りする。幸福度 bi を加算
C: 家で宿題をする。幸福度 ci を加算

の三択の中から好きなものを選ぶことができます。ただし、2 日連続で A, B, C のうちの同一種類の活動を選択をすることはできません。この制約下で最終的に得られる幸福度の総和を最大にせよ。
---------------------------------------------------------------------------
0日目は幸福度は 0 らしいので、初日に A[0] = A, A[1] = B , A[2] = C と
アクティビティを行う 3 パターンの start が想定されます。
このように考えると、アクティビティは日を追うごとに複雑になるので、
前述にあるようにメモが 1 行だけでは追い付かなくなります。

上図は貰う DP で考えています。
勿論、2 日目の幸福度を求めるためには前日の情報が必要です。
考慮と言っても、幸福度が高くなる経路が何方かだったかを
確認してメモできれば OK です。

cal_fortune.py

# fortune point
A = [0,1,3]
# kind of activity
K = 3
# total days
D = 10

ANS = 0

# memo table
memo = [[0 for l in range(len(A))] for m in range(D)]

# First day 
memo[1][0] = A[0]
memo[1][1] = A[1]
memo[1][2] = A[2]

for i in range(2,D,1):    # Day
    for j in range(K):    # Activity 
        for k in range(K):# Other Activity
            if j == k:
                continue
            memo[i][j]=max(A[j],A[j]+memo[i-1][k])

# list the point during period
for m in range(D):
    print(f"{m}th day is {memo[m]}")

for n in range(K):
    ANS = max(ANS,memo[9][n])
print(ANS)

実行結果.py

0th day is [0, 0, 0]
1th day is [0, 1, 3]
2th day is [3, 4, 4]
3th day is [4, 5, 7]
4th day is [7, 8, 8]
5th day is [8, 9, 11]
6th day is [11, 12, 12]
7th day is [12, 13, 15]
8th day is [15, 16, 16]
9th day is [16, 17, 19]
19

しっかりとしたイメージを作れば何とか書けますね。
お疲れ様でした ^^) _旦~~

12/02 update
新しい問題にチャレンジしてみました。
こちらです。

はじめ、高橋君の満腹度は H です。N 日間のそれぞれの日について、その日にとる食事を次の 3 種類の中から 1 つ選びます。
・普通の食事: A 円の出費をして、満腹度が B 増える。
・質素な食事: C 円の出費をして、満腹度が D 増える。（ただし、C<A かつ D<B）
・食事抜き: 出費なしで、満腹度が E 減る。
厳しく節約すれば出費を抑えることができますが、あまりに節約しすぎて体調を崩してしまってはいけないため、
N 日間で一度も満腹度が 0 以下にならないようにしなければなりません。

高橋君は最低何円の食費で N 日間を乗り切ることができるでしょうか？

今まで通りの考え方だとハマります。
なぜなら。。。

今後、綺麗にするかもしれないですけど、
とり急ぎ別のアイディアをメモレベルですが載せておきます。

横軸を空腹度としました。該当するセルを追いかけてメモを更新するためには
次どこに行くべきなのかを更に別で記録する必要があります。
何やら訳が分からなくなるので、表全部を一個ずつ更新することにします。

takahashi_survival.py

# N,H = map(int,input().split())
# A,B,C,D,E = map(int,input().split())

N,H = 4,5
A,B,C,D,E = 100,4,60,1,4

# N,H = 10,1
# A,B,C,D,E = 5000,2,2000,1,300

# INF = float("inf")
# ANS = float("inf")
INF = A*2
ANS = A*2

MAX_LIFE = H+B*N
dp = [[INF for m in range(MAX_LIFE)] for n in range(N+1)]

dp[0][H] = 0

for i in range(N):
    for j in range(MAX_LIFE):
        if MAX_LIFE - (j + B) > 0:
            dp[i+1][j+B] = min(dp[i+1][j+B],dp[i][j]+A)
        if MAX_LIFE - (j + D) > 0:
            dp[i+1][j+D] = min(dp[i+1][j+D],dp[i][j]+C)
        if (j - E) > 0:
            dp[i+1][j-E] = min(dp[i+1][j-E],dp[i][j])

for l in range(MAX_LIFE):
    ANS = min(ANS,dp[N][l])

print(ANS)

一応、欲しい答えは出たけど、
AtCoder 先生曰く、実行時間制限超過らしい。
厳しいですね(笑)