DPさん、お手柔らかに _12/2 update

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

前回、[ここ](https://qiita.com/AKpirion/items/f28661dccc21c2270189) で最後に 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 を格納します。
![図1.PNG](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/737344/d8d69273-5a8b-4c3c-b1e9-c892878a7e02.png)
**i = 1 のとき**
memo[1] にある 7 と
memo[1]+A[1] の 1 とでは、どちらが大きいでしょうか？
前者ですよね？
この結果は memo[2] に格納します。
![図2.PNG](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/737344/7ac8fe3b-ae1f-411e-13d6-1cf13365b5c7.png)
**i = 2 のとき**
memo[2] にある 7 と
memo[2] + A[2] の 16 はどちらが大きいですか？
はい、結果を格納します。
![図3.PNG](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/737344/ba06d27f-136e-3b40-bb63-bc1af07736f5.png)
最後に 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 ) を算出することが出来ます。

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

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

```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
![図4.PNG](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/737344/2f87d613-e978-ee51-706a-6b11c930cf32.png)
配る 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]からが本番です。
![図5.PNG](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/737344/f275aea2-b9da-285d-11f8-1e4d1eb1891e.png)
最小値 2 を探し出しました。
次の memo[3] は memo[0] - memo[2] の 3 つ中から最適値を見つけます。
![図6.PNG](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/737344/3e5794c5-5d6f-ae53-0501-1bf53eb66cb7.png)
残りの作業は同じ内容なので補足説明は省きます。
![図7.PNG](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/737344/332ae694-cf4e-4a12-6a74-8870c3b33bfc.png)
![図8.PNG](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/737344/f99bce1a-814b-07cc-bb28-5dff5a35a2fe.png)
![図9.PNG](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/737344/88c460b7-e319-e456-dce4-96bb0f57c792.png)


行ってみたいなー、幸福の国。。
っというわけで、以下の問題にも挑戦しました。
勿論、問題は[**ここ**](https://qiita.com/drken/items/dc53c683d6de8aeacf5a)を参照にしています

*---------------------------------------------------------------------------*
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 行だけでは追い付かなくなります。
![図10.PNG](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/737344/d0b41b82-ac02-24c4-909f-e9d7ac88a08f.png)
上図は貰う 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**
新しい問題にチャレンジしてみました。
[**こちら**](https://atcoder.jp/contests/abc013/tasks/abc013_3)です。

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

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

-------------------------------------------------------------
今まで通りの考え方だとハマります。
なぜなら。。。
![図11.PNG](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/737344/12dfc74d-aab2-941a-3628-a5b0b500011b.png)
今後、綺麗にするかもしれないですけど、
とり急ぎ別のアイディアをメモレベルですが載せておきます。
![IMG_0065.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/737344/1b3bc0b8-d0c2-6d07-6daa-64474806a55b.jpeg)
横軸を空腹度としました。該当するセルを追いかけてメモを更新するためには
次どこに行くべきなのかを更に別で記録する必要があります。
何やら訳が分からなくなるので、表全部を一個ずつ更新することにします。

```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 先生](https://atcoder.jp/contests/abc013/tasks/abc013_3)曰く、実行時間制限超過らしい。
厳しいですね(笑)