H - Grid 1（動的計画法⑩）

問題

縦 H 行、横 W 列のグリッドがあります。 

上から i 行目、左から j 列目のマスを (i,j) で表します。

各 i, j ( 1 ≦ i ≦ H, 1 ≦ j ≦ W) について、マス (i, j) の情報が文字 a[i, j] によって与えられます。

a[i, j] が . ならばマス (i,j) は空マスであり、a[i, j] が # ならばマス (i, j) は壁のマスです。

マス (1, 1) および (H, W) は空のマスであることが保証されています。

マス (1, 1) から出発し、右または下に隣り合う空マスへの移動を繰り返すことで、マス (H,W) まで辿り着こうとしています。

マス (1, 1) から (H, W) までの経路は何通りあるでしょうか。

答えは非常に大きくなりうるので、10**9 + 7 で割った余りを求めてください。

解法・ソースコード

単純に 左上から右下までの経路 を求めるという問題で、移動するたびにカウントアップすれば経路の数を求めることができます。

もちろん移動先が壁の場合は、カウントアップしません。

また、問題文の最後にあるように、109 + 7を超えた場合は余りを求めるために 109 + 7を引いています。

（最後に 10**9 + 7 で割ってその余りを求める方法もありますが、カウントアップ途中で数字が大きくなりオーバーフローする可能性があります）

[Google Colaboratory]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#--------- 入力例1 ----------
mp = ['...#',
      '.#..',
      '....']
#--------- 入力例2 ----------
# mp = ['..',
#       '#.',
#       '..',
#       '.#',
#       '..']
#--------- 入力例3 ----------
# mp = ['..#..',
#       '.....',
#       '#...#',
#       '.....',
#       '..#..']
#--------- 入力例4 ----------
# mp = ['....................',
#       '....................',
#       '....................',
#       '....................',
#       '....................',
#       '....................',
#       '....................',
#       '....................',
#       '....................',
#       '....................',
#       '....................',
#       '....................',
#       '....................',
#       '....................',
#       '....................',
#       '....................',
#       '....................',
#       '....................',
#       '....................',
#       '....................']
#----------------------------
H, W = len(mp), len(mp[0])
MOD = 10**9 + 7

# メモ化テーブル初期化
memo = [[0] * W for _ in range(H)]
# 初期条件
memo[0][0] = 1

# 全マス目を探索
for i in range(H):
    for j in range(W):
        if i + 1 < H and mp[i + 1][j] == '.':
            memo[i + 1][j] += memo[i][j]    # カウントアップ
            # 計算の途中で余りをとる
            if memo[i + 1][j] >= MOD:
                memo[i + 1][j] -= MOD
        if j + 1 < W and mp[i][j + 1] == '.':
            memo[i][j + 1] += memo[i][j]    # カウントアップ
            # 計算の途中で余りをとる
            if memo[i][j + 1] >= MOD:
                memo[i][j + 1] -= MOD

print('解：', memo[H - 1][W - 1])

[実行結果(入力例1)]

解： 3

経路は 3 通りあります。

[実行結果(入力例2)]

解： 0

経路が存在しません。

[実行結果(入力例3)]

解： 24

経路は 24 通りあります。

[実行結果(入力例4)]

解： 345263555

経路は 345263555 通りあります。

途中で 10**9 + 7 を超えているため、その余りが経路数となります。

Longest Path（トポロジカルソート）

トポロジカルソート

トポロジカルソート は、グラフ理論において、有向非巡回グラフの各ノードを順序付けして、どのノードもその出力辺の先のノードより前にくるように並べることです。

有向非巡回グラフは必ず トポロジカルソート することができます。

タスク間に依存関係がある場合、どんな順番でタスクをこなせば良いかを決めるのに役立つアルゴリズムです。

問題

頂点数がＮ、辺の数がＭの有向グラフ G があります。 

頂点には 1,2,…,N と番号が振られています。 

各 i (1 ≦ i ≦ M) について、i 番目の有向辺は頂点 x_i から y_i へ張られています。

G は有向閉路を含みません。

G の有向パスのうち、最長のものの長さを求めてください。 

（有向パスの長さとは、有向パスに含まれる辺の本数のことです。）

解法・ソースコード

この問題は、頂点を トポロジカルソート で並べ替えて、その順番に有向パスでの通過数をカウントすることで解くことができます。

[Google Colaboratory]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#--------- 入力例1 ----------
# ノードの数
n = 4
# 全エッジ（ x → y ）
lst = [(1, 2),
       (1, 3),
       (3, 2),
       (2, 4),
       (3, 4)]
#--------- 入力例2 ----------
# # ノードの数
# n = 6
# # 全エッジ（ x → y ）
# lst = [(2, 3),
#        (4, 5),
#        (5, 6)]
#--------- 入力例3 ----------
# # ノードの数
# n = 5
# # 全エッジ（ x → y ）
# lst = [(5, 3),
#        (2, 3),
#        (2, 4),
#        (5, 2),
#        (5, 1),
#        (1, 4),
#        (4, 3),
#        (1, 3)]
#----------------------------
from collections import defaultdict 

# トポロジーソートを行うクラス
class Graph: 
    def __init__(self,vertices): 
        self.graph = defaultdict(list) 
        self.V = vertices
  
    def addEdge(self,u,v): 
        self.graph[u].append(v) 
  
    def topologicalSortUtil(self, v, visited,stack): 
        visited[v] = True
        for i in self.graph[v]: 
            if visited[i] == False: 
                self.topologicalSortUtil(i,visited,stack) 
  
        stack.insert(0,v) 
  
    def topologicalSort(self): 
        visited = [False]*self.V 
        stack =[] 
  
        for i in range(self.V): 
            if visited[i] == False: 
                self.topologicalSortUtil(i,visited,stack) 
        return stack

g = Graph(n + 1)    # 0スタートなので頂点を１つ多めに
for a, b in lst:
    g.addEdge(a, b)     # 有向パス追加

print ("トポロジカルソートの結果：", g.topologicalSort())

# トポロジカルソート順に通過数をカウント
memo = {}   # カウント（キー：頂点番号、バリュー：通過数）
for x in list(g.topologicalSort()):
    for a, b in lst:
        if x == a:
            memo[b] = memo.get(a, 0) + 1

print('解：', max(memo.values()))

[実行結果(入力例1)]

トポロジカルソートの結果： [1, 3, 2, 4, 0]

解： 3

1→3→2→4 の有向パスが最長になります。

[実行結果(入力例2)]

トポロジカルソートの結果： [4, 5, 6, 2, 3, 1, 0]

解： 2

4→5→6 の有向パスが最長になります。

[実行結果(入力例3)]

トポロジカルソートの結果： [5, 2, 1, 4, 3, 0]

解： 3

5→2→4→3、5→1→4→3 の有向パスが最長になります。

F - LCS（動的計画法⑨）

問題

文字列 a および ｂ が与えられます。

a の部分列かつ ｂ の部分列であるような文字列のうち、最長のものをひとつ求めてください。

【注釈】

文字列 x の 部分列 とは、x から 0 個以上の文字を取り除いた後、

残りの文字を元の順序で連結して得られる文字列のことです。

解法・ソースコード

最長共通部分列 の長さを求める問題は以前の記事で解いています。

最長共通部分列（動的計画法③）- https://ailogsite.netlify.app/2022/12/16/2022/1216/

今回は、さらに「最長共通部分列を具体的にどれか1つ」求める方法を考えます。

基本的な考え方としては メモ化テーブルの 終端ノード memo[(len(a), len(b)] から順に どのノードから更新されて来たのか、その元となる部分を辿って行く ことになります。

メモ化テーブルの値を見ながら、今いる ノード (i, j) がどのノードから更新されて来たのかを特定し、求める 最長共通部分の文字列 を復元していきます。

[Google Colaboratory]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#---------- 入力例1 ----------
a = 'axyb'
b = 'abyxb'
#---------- 入力例2 ----------
# a = 'aa'
# b = 'xayaz'
#---------- 入力例3 ----------
# a = 'a'
# b = 'z'
#---------- 入力例4 ----------
# a = 'abracadabra'
# b = 'avadakedavra'
#-----------------------------
# メモ化テーブル
memo = {}
x = ''
for i, a1 in enumerate(a):
    for j, b1 in enumerate(b):
        # print(i,j,a1,b1)
        if a1 == b1:
            # print('  #', a1,i,j)
            memo[i + 1, j + 1] = memo.get((i, j), 0) + 1
        else:
            memo[i + 1, j + 1] = max(memo.get((i, j + 1), 0), memo.get((i + 1, j), 0))
print('長さ：', memo[(len(a), len(b))])

# メモ化テーブルの値を見ながら、今いるノード (i,j)(i,j) がどのノードから更新されて来たのかを特定する
i, j = len(a), len(b)

res = ''    # 求める最長の文字列   
while i > 0 and j > 0:
    if memo.get((i, j), 0) == memo.get((i - 1, j), 0):    # (i-1, j) -> (i, j) と更新されていた場合
        i -= 1
    elif memo.get((i, j), 0) == memo.get((i, j - 1), 0):  # (i, j-1) -> (i, j) と更新されていた場合
        j -= 1
    else:                           # (i-1, j-1) -> (i, j) と更新されていた場合
        res = a[i - 1] + res        # 求める文字列を復元する　a[j - 1]でも可
        i -= 1
        j -= 1
print('解：', res)

[実行結果(入力例1)]

長さ： 3
解： axb

答えは axb または ayb です。 どちらを出力しても正解です。

[実行結果(入力例2)]

長さ： 2
解： aa

答えは aa となります。

[実行結果(入力例3)]

長さ： 0   
解：

答えは (空文字列) です。

[実行結果(入力例4)]

長さ： 7
解： aaadara

答えは aaadara となります。

ナップサック問題（動的計画法⑧）

問題

N 個の品物があります。 品物には 1,2,…,N と番号が振られています。

各 i (1≦i≦N) について、品物 i の重さは w_i で、価値は v_iです。

N 個の品物のうちいくつかを選び、ナップサックに入れて持ちかえります。 

ナップサックの容量は W であり、持ち帰る品物の重さの総和は W 以下でなければなりません。

持ち帰る品物の価値の総和の最大値を求めてください。

解法・ソースコード

今回は、もっとも単純な ナップサック問題 のおさらいです。

品物ごと、許容範囲の重さごと にループを回して、品物を入れるか入れないかを選択し、価値の高くなる方の選択結果を メモ化テーブル に格納していきます。

[Google Colaboratory]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#--------- 入力例1 ----------
w = 8
items = [{'weight':3, 'value':30},
         {'weight':4, 'value':50},
         {'weight':5, 'value':60}]
#--------- 入力例2 ----------
# w = 5
# items = [{'weight':1, 'value':1000000000},
#          {'weight':1, 'value':1000000000},
#          {'weight':1, 'value':1000000000},
#          {'weight':1, 'value':1000000000},
#          {'weight':1, 'value':1000000000}]
#--------- 入力例3 ----------
# w = 15
# items = [{'weight':6, 'value':5},
#          {'weight':5, 'value':6},
#          {'weight':6, 'value':4},
#          {'weight':6, 'value':6},
#          {'weight':3, 'value':5},
#          {'weight':7, 'value':2}]
#----------------------------
n = len(items)    # 品物の総数

# メモ化テーブル（動的計画法用）
memo = {}

for i, item in enumerate(items):    # 品物ごとにループ
    for j in range(w + 1):          # 重さ＋1までループ
        if j < items[i]['weight']:          # 重さが許容範囲外の場合
            # 品物を入れない
            memo[i + 1, j] = memo.get((i, j), 0)
        else:                               # 重さが許容範囲内の場合
            # 品物を入れない場合
            a = memo.get((i, j), 0)
            # 品物を入れる場合（許容範囲の重さを減らし、価値を増やす）
            b = memo.get((i, j - items[i]['weight']), 0) + items[i]['value']
            memo[i + 1, j] = max(a, b)    # 価値が高いほうを選択

print('【メモ化テーブルの内容】')
for i, item in enumerate(items):    # 品物ごとにループ
    for j in range(w):              # 重さごとにループ
        print(str(memo[i+1, j+1]).rjust(2, ' '), end=' ')
    print()
print('-----------------------')
print('解（価値の総和の最大値）：', memo[len(items), w])

[実行結果(入力例1)]

【メモ化テーブルの内容】
 0  0 30 30 30 30 30 30 
 0  0 30 50 50 50 80 80 
 0  0 30 50 60 60 80 90 
-----------------------
解（価値の総和の最大値）： 90

品物 1,3 を選ぶと、重さの総和は 3+5=8 となり、価値の総和は 30+60=90 となります。

[実行結果(入力例2)]

【メモ化テーブルの内容】
1000000000 1000000000 1000000000 1000000000 1000000000 
1000000000 2000000000 2000000000 2000000000 2000000000 
1000000000 2000000000 3000000000 3000000000 3000000000 
1000000000 2000000000 3000000000 4000000000 4000000000 
1000000000 2000000000 3000000000 4000000000 5000000000 
-----------------------
解（価値の総和の最大値）： 5000000000

全部の品物 を持っていくことができるので、価値の総和は 5000000000 となります。

[実行結果(入力例3)]

【メモ化テーブルの内容】
 0  0  0  0  0  5  5  5  5  5  5  5  5  5  5 
 0  0  0  0  6  6  6  6  6  6 11 11 11 11 11 
 0  0  0  0  6  6  6  6  6  6 11 11 11 11 11 
 0  0  0  0  6  6  6  6  6  6 12 12 12 12 12 
 0  0  5  5  6  6  6 11 11 11 12 12 12 17 17 
 0  0  5  5  6  6  6 11 11 11 12 12 12 17 17 
-----------------------
解（価値の総和の最大値）： 17

品物 2,4,5 を選ぶと、重さの総和は 5+6+3=14 で価値の総和は 6+6+5=17 となります。

夏休み（動的計画法⑦）

問題

 N 日の夏休みがあります。
 
各 i (1 ≦ i ≦ N) について、i 日目には次の活動のうちひとつを選んで行います。

　A: 海で泳ぐ。 幸福度 a_i を得る。

　B: 山で虫取りをする。 幸福度 b_i を得る。
　
　C: 家で宿題をする。 幸福度 c_i を得る。

2 日以上連続で同じ活動を行うことはできません。

幸福度の 総和の最大値 を求めてください。

解法・ソースコード

Ｎ日目にそれぞれの活動を行った場合の幸福度を管理するためのメモ化テーブル（動的計画法のための２次元配列）を用意します。

i - 1日目に jの活動、i日目に kの活動 を行う場合の 幸福度memo1 を計算し、一番大きいものを memo[i + 1][k] に代入します。

[Google Colaboratory]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#--------- 入力例1 ----------
lst = [(10, 40, 70),
       (20, 50, 80),
       (30, 60, 90)]
#--------- 入力例2 ----------
# lst = [(100, 10, 1)]
#--------- 入力例3 ----------
# lst = [(6, 7, 8),
#        (8, 8, 3),
#        (2, 5, 2),
#        (7, 8, 6),
#        (4, 6, 8),
#        (2, 3, 4),
#        (7, 5, 1)]
#----------------------------
n = len(lst)    # 夏休みの日数
# メモ化テーブル（動的計画法用の2次元配列。第１引数：夏休みの日数＋１日、第２引数：３つの活動）
memo = [[0 for i in range(3)] for j in range(n + 1)]

for i in range(n):          # 夏休みの日数分ループ
    for j in range(3):      # 前日の活動 
        for k in range(3):  # 当日の活動
            if j == k:      # 前日と同じ活動はできない
                continue
            # i-1日目(前日)にjの活動、i日目にkの活動を行う場合の幸福度
            memo1 = memo[i][j] + lst[i][k]
            # memo[i + 1][k]はi日目にkを行ったときの得られる累積の最大幸福度
            memo[i + 1][k] = max(memo[i + 1][k], memo1)

for i in range(n + 1):
    print(f'{i}日目の累積最大幸福度', memo[i])
print('解（幸福度の総和の最大値）：',max(memo[n]))

[実行結果(入力例1)]

0日目の累積最大幸福度 [0, 0, 0]

1日目の累積最大幸福度 [10, 40, 70]

2日目の累積最大幸福度 [90, 120, 120]

3日目の累積最大幸福度 [150, 180, 210]

解（幸福度の総和の最大値）： 210

C, B, C の順に活動を行うと、幸福度の総和は 70 + 50 + 90 = 210 となります。

[実行結果(入力例2)]

0日目の累積最大幸福度 [0, 0, 0]

1日目の累積最大幸福度 [100, 10, 1]

解（幸福度の総和の最大値）： 100

A の活動を行うと最大幸福になるのは明らかです。

[実行結果(入力例3)]

0日目の累積最大幸福度 [0, 0, 0]

1日目の累積最大幸福度 [6, 7, 8]

2日目の累積最大幸福度 [16, 16, 10]

3日目の累積最大幸福度 [18, 21, 18]

4日目の累積最大幸福度 [28, 26, 27]

5日目の累積最大幸福度 [31, 34, 36]

6日目の累積最大幸福度 [38, 39, 38]

7日目の累積最大幸福度 [46, 43, 40]

解（幸福度の総和の最大値）： 46

C, A, B, A, C, B, A の順に活動を行えば最大幸福になります。

文字列判定（動的計画法⑥）

問題

英小文字の文字列 Ｓ があります。

空文字 Ｔ に対して次の操作を繰り返すことで、Ｓ＝Ｔ である状態にできるかどうかを判定してください。

「Ｔ の末尾に"dream"、"dreamer"、"erase"、"eraser"のいずれかを追加する」

解法・ソースコード

まず 再帰関数 を用いた 全探索解法 を考えます。

次のように 再帰関数 を定義します。

rec(i) ← 文字列Ｓの最初のｉ文字分が、"dream"、"dreamer"、"erase"、"eraser"の連結で作れるかどうかを表すブール値（True／False）

文字列Ｓの長さをＮとしたとき、rec(n)が最終的な答えとなります。

rec(i)を求めるために、次の４パターンに分けて考えます。

  • s[0:i]の末尾を”erase”で区切る場合
    rec(i - 5)がTrue かつ s[0:1]の最後の５文字が”erase”であるならば、rec(i)はTrue
  • s[0:i]の末尾を”eraser”で区切る場合
    rec(i - 6)がTrue かつ s[0:1]の最後の５文字が”eraser”であるならば、rec(i)はTrue
  • s[0:i]の末尾を”dream”で区切る場合
    rec(i - 5)がTrue かつ s[0:1]の最後の５文字が”dream”であるならば、rec(i)はTrue
  • s[0:i]の末尾を”dreamer”で区切る場合
    rec(i - 7)がTrue かつ s[0:1]の最後の５文字が”dreamer”であるならば、rec(i)はTrue

この 再帰関数 rec(i) を踏まえて、動的計画法 を表す 配列memo を次のように定義します。

memo[i] ← s[0:i]が、"dream"、"dreamer"、"erase"、"eraser"の連結で作れるどうかを表すブール値（True／False）

memo[0]、memo[1]、…、memo[n] の値を順番に求めていきます。

[Google Colaboratory]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#---------- 入力例 ----------
s = 'erasedream'
#----------------------------
n = len(s)      # 文字列の長さ
memo = [False] * (n + 1)    # メモ化テーブル（動的計画法用の配列）
memo[0] = True

# memo[0]、memo[1]、…、memo[n]を順に求める
for i in range(n + 1):
    if i >= 5 and memo[i - 5] and s[i - 5:i] == 'erase':
        print(i, 'erase')
        memo[i] = True
    if i >= 6 and memo[i - 6] and s[i - 6:i] == 'eraser':
        print(i, 'eraser')
        memo[i] = True
    if i >= 5 and memo[i - 5] and s[i - 5:i] == 'dream':
        print(i, 'dream')
        memo[i] = True
    if i >= 7 and memo[i - 7] and s[i - 7:i] == 'dreamer':
        print(i, 'dreamer')
        memo[i] = True
print('memo', memo)
print('解：Yes' if memo[n] else '解：No')

[実行結果]

5 erase

10 dream

memo [True, False, False, False, False, True, False, False, False, False, True]

解：Yes

“erase” + “dream” で、“erasedream” という文字列が作成できるので、正解は “Yes”（作成できる） となります。

カエルの段差移動2（動的計画法⑤）

動的計画法

カエルが最小コストで段差を移動する問題の２つめを、動的計画法 を使って解いていきます。

[問題]

Ｎ個の足場があります。 足場には 1, 2, …, N と番号が振られています。

各 i (1 ≦ i ≦  N) について、足場 i の高さは h_i です。

最初にカエルは、足場1にいます。

カエルは次の行動を何回か繰り返し、足場Ｎまで辿り着こうとしています。

足場 i にいるとき、足場 i + 1, i + 2, …, i + K のどれかへジャンプする。 

このとき、ジャンプ先の足場を j とすると、コスト ∣h_i − h_j∣ (差分の絶対値)を

コストとして支払う必要があります。

カエルが足場 N に辿り着くまでに支払うコストの 総和の最小値 を求めてください。

解法・ソースコード

前回の問題との違いは、ジャンプする幅が i+1, i+2 だけではなく、i + K と可変になっているところです。

ただし、前回の処理で +1, +2 の２パターンで処理していた個所を、K回ループで回す 処理に変えるだけなので、ほんの少しの修正で対応することが可能です。

修正したソースコードは次のようになります。

[Google Colaboratory]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#--------- 入力例1 ----------
k=3
lst = [10, 30, 40, 50, 20]
#--------- 入力例2 ----------
# k=1
# lst = [10, 20, 10]
#--------- 入力例4 ----------
# k=100
# lst = [10, 10]
#--------- 入力例4 ----------
# k=4
# lst = [40, 10, 20, 70, 80, 10, 20, 70, 80, 60]
#----------------------------
n = len(lst)      # 段差の数

memo = [float('inf')] * n

memo[0] = 0
for i in range(n):
    for x in range(1, k + 1):
        if i - x >= 0:
            memo[i] = min(memo[i], memo[i - x] + abs(lst[i] - lst[i - x]))
print(memo[n-1])

[実行結果（入力例1）]

30

足場 1 → 2 → 5 と移動すると、コストの総和は ∣ 10 − 30 ∣ + ∣ 30 − 20 ∣ = 30 となります。

[実行結果（入力例2）]

20

足場 1 → 2 → 3 と移動すると、コストの総和は ∣ 10 − 20 ∣ + ∣ 20 − 10 ∣ = 20 となります。

[実行結果（入力例3）]

0

足場 1 → 2 と移動すると、コストの総和は ∣ 10 − 10 ∣ = 0 となります。

[実行結果（入力例4）]

40

足場 1 → 4 → 8 → 10 と移動すると、コストの総和は ∣ 40 − 70 ∣ + ∣ 70 − 70 ∣ + ∣ 70 − 60 ∣ = 40 となります。

カエルの段差移動（動的計画法④）

動的計画法

カエルが最小コストで段差を移動する問題を、動的計画法 を使って解いていきます。

[問題]

Ｎ個の足場があります。 足場には 1,2,…,N と番号が振られています。

各 i (1 ≦ i ≦  N) について、足場 i の高さは h_i です。

最初にカエルは、足場 1 にいます。

カエルは次の行動を何回か繰り返し、足場Nまで辿り着こうとしています。

足場 i にいるとき、足場 i + 1 または i + 2 へジャンプします。

このとき、ジャンプ先の足場を j とすると、コスト ∣h_i − h_j∣ (差分の絶対値)を支払う必要があります。

カエルが足場 N に辿り着くまでに支払うコストの 総和の最小値 を求めてください。

解法・ソースコード

メモ化テーブル memo[i] を頂点iへと至る最短経路を表していると定義します。

memo[i] の値を求めるために、次の２つを比較します。

  • 頂点 i - 1まで最短経路で行ってから、頂点 i へと至る方法の最小コスト
    memo[i - 1] + abs(h[i] - h[i - 1])
  • 頂点 i - 2まで最短経路で行ってから、頂点 i へと至る方法の最小コスト
    memo[i - 2] + abs(h[i] - h[i - 2])

memo[i] の値は、これらのうちの 最小値 となります。

以上を踏まえて実装すると以下のようなソースになります。

[Google Colaboratory]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#--------- 入力例1 ----------
lst = [10, 30, 40, 20]
#--------- 入力例2 ----------
# lst = [10, 10]
#--------- 入力例3 ----------
# lst = [30, 10, 60, 10, 60, 50]
#----------------------------
n = len(lst)    # 足場の数

memo = [float('inf')] * n
memo[0] = 0

for i in range(n):
    if i - 1 >= 0:
        memo[i] = min(memo[i], memo[i - 1] + abs(lst[i] - lst[i - 1]))
    if i - 2 >= 0:
        memo[i] = min(memo[i], memo[i - 2] + abs(lst[i] - lst[i - 2]))
print(memo[n - 1])

[実行結果（入力例1）]

30

足場 1 → 2 → 4 と移動すると、コストの総和は ∣10 − 30∣ + ∣30 − 20∣ = 30 となります。

[実行結果（入力例2）]

0

足場 1 → 2 と移動すると、コストの総和は ∣ 10 − 10 ∣ = 0 となります。

[実行結果（入力例3）]

40

足場 1 → 3 → 5 → 6 と移動すると、コストの総和は ∣ 30 − 60 ∣ + ∣60 − 60 ∣ + ∣ 60 − 50 ∣ = 40 となります。

最長共通部分列（動的計画法③）

最長共通部分列

部分列 は系列のいくつかの要素を取り出してできた系列のことです。

二つの系列の共通の部分列を 共通部分列 と言います。

共通部分列のうちもっとも長いものを 最長共通部分列 と言います。

最長共通部分列 を求める問題を 動的計画法 を使って解いていきます。

問題

２つの文字列があります。

これら２つの共通部分列の長さの最大値を求めて下さい。

解法・ソースコード

メモ化テーブル を次のように定義します。

memo[i][j] は、【１つめの文字列のｉ文字まで】と【２つめの文字列のｊ文字まで】の

最長共通部分列の長さ

この定義を踏まえて、漸化式 を作成し 動的計画法（メモ化テーブル） を実装すると次のようになります。

[Google Colaboratory]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#---------- 入力例 ----------
a = 'ABCBDAB'
b = 'BDCABA'
#----------------------------
# メモ化テーブル
memo = {}

for i, a1 in enumerate(a):
    for j, b1 in enumerate(b):
        if a1 == b1:    # 文字が一致した場合
            # 最長共通部分列の長さを１つ増やす
            memo[i + 1, j + 1] = memo.get((i, j), 0) + 1
        else:           # 文字が一致しない場合
            # これまでの最長共通部分列で長いほうを選択
            memo[i + 1, j + 1] = max(memo.get((i, j + 1), 0), memo.get((i + 1, j), 0))

print('解：', memo[(len(a), len(b))])

[実行結果]

解： 4

解は 4 となりました。

２つの文字列を確認すると 最長共通部分列 が B, C, B, A となっていて解が正しいことが分かります。

ナップサック問題（動的計画法②）

動的計画法（順方向）

前回は 動的計画法 を使ってナップサック問題を解きましたが、再帰関数に合わせてループの順番が 逆方向 になっていました。

今回は、このループの順番を 順方向 に変えてみます。

[ナップサック問題]

Ｎ個の品物があります。

それぞれの品物の 重さ(weight) と 価値(value) は分かっています。

これらの品物からいくつか選んでナップサックに詰めていきます。

ナップサックにい列品物の総和は capacity を超えてはいけません。

選んだ品物の価値の総和として考えられる最大値を求めて下さい。

解法・ソースコード

ループを 順方向 に変えるためには、ループ文 と 漸化式 を少し変更する必要がありますが、根本的な内容は前回記事の処理と変わりません。

[Google Colaboratory]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#---------- 入力例 ----------
items = [{'weight':2, 'value':3},
         {'weight':1, 'value':2},
         {'weight':3, 'value':4},
         {'weight':2, 'value':2}]
capacity = 5
#----------------------------
# 動的配列
dp = {}
for i in range(0, len(items) ):             # アイテムを順方向にループ
    for j in range(capacity + 1):           # 重さを順番にループ
        if j < items[i]['weight']:          # 重さが許容範囲外の場合
            dp[i + 1, j] = dp.get((i, j), 0)
        else:                               # 重さが許容範囲内の場合
            # 品物を入れない場合
            a = dp.get((i, j), 0)
            # 品物を入れる場合（許容範囲の重さを減らし、価値を増やす）
            b = dp.get((i, j - items[i]['weight']), 0) + items[i]['value']
            dp[i + 1, j] = max(a, b)        # 価値が高いほうを選択

print('解：', dp[len(items), 5])

ループを 順方向 に変えることで、ループ文 や 漸化式 がシンプルで分かりやすくなったのではないでしょうか。

[実行結果]

解： 7

解（価値の総和の最大値）はこれまで同様 7 となっています。