関数呼び出しを用いたプログラムから動的計画法のプログラムを書く時に用いる再帰関係について
配列が与えられ、連続する1の最も長い個数を出力するプログラムを書いています。
例えば、入力が[1,1,0,0,0,1,1,1,1,0,0]なら、4が出力されます。
困っていること
再帰表現を用いたプログラムは正しい出力が得られるのですが、関数countones(A, i)内の再帰関係を以下のように分割し、動的計画法で書いたプログラムも正しく動いたのですが、再帰関係において理解できないことがあります。
<関数countones(A, i)内の再帰関係>
・countones(A,i) = 1 if i = len(A) and A[i] = 1
・countones(A,i) = countones(A,i+1)+1 if i<len(A) and A[i] = 1
・countones(A,i) = 0 if A[i] = 0
上記の2つ目の
・countones(A,i) = countones(A,i+1)+1 if i<len(A) and A[i] = 1
がなぜ成り立つのか動的計画法のプログラムにおいて
T[i] = T[i+1] + 1
の部分で何をやっているのかと合わせて理解できません。
プログラムのどの部分で確認できるのか、もしくはなぜこの再帰関係が成り立つのか説明いただきたいです。
実行しているプログラム
動的計画法で書いたプログラム
def longestnum2(A : list) -> int:
max = 0
T = [0] * len(A)
for j in range(len(A)):
i = (len(A) - 1) - j
if A[i] == 0:
T[i] = 0
elif i == len(A)-1 and A[i] == 1:
T[i] = 1
else:
T[i] = T[i+1] + 1
if max < T[i]:
max = T[i]
return max
A = [1,1,0,0,0,1,1,1,1,0,0]
print(longestnum2(A)) #4
試したこと
関数呼び出しを用いたプログラム
def loggestnum(A):
max = 0
for i in range(len(A)):
p = countones(A, i)
if (max<p):
max = p
return max
def countones(A,i):
p = 0
j = i
while j <= len(A) and A[j] == 1:
p = p+1
j = j+1
return p
A = [1,1,0,0,0,1,1,1,1,0,0]
print(loggestnum(A)) #4