MIT OCW のコースを通じて、動的プログラミングの概念を理解しようとしています。OCWの動画での説明は素晴らしいのですが、説明をコードに落とし込むまではよくわからない気がします。実装中、ここの講義ノート、特にノートの 3 ページからいくつかのメモを参照します。
問題は、数学表記の一部をコードに変換する方法がわからないことです。これが私が実装したソリューションの一部です（そしてそれが正しく実装されていると思います）：
import math
paragraph = "Some long lorem ipsum text."
words = paragraph.split(" ")
# Count total length for all strings in a list of strings.
# This function will be used by the badness function below.
def total_length(str_arr):
total = 0
for string in str_arr:
total = total + len(string)
total = total + len(str_arr) # spaces
return total
# Calculate the badness score for a word.
# str_arr is assumed be send as word[i:j] as in the notes
# we don't make i and j as argument since it will require
# global vars then.
def badness(str_arr, page_width):
line_len = total_length(str_arr)
if line_len > page_width:
return float('nan')
else:
return math.pow(page_width - line_len, 3)
今、私が理解していないのは、講義ノートのポイント 3 から 5 です。私は文字通り理解しておらず、それらの実装をどこから始めればよいかわかりません。これまでのところ、次のように、単語のリストを繰り返し、行末と思われる各行の悪さを数えてみました。
def justifier(str_arr, page_width):
paragraph = str_arr
par_len = len(paragraph)
result = [] # stores each line as list of strings
for i in range(0, par_len):
if i == (par_len - 1):
result.append(paragraph)
else:
dag = [badness(paragraph[i:j], page_width) + justifier(paragraph[j:], page_width) for j in range(i + 1, par_len + 1)]
# Should I do a min(dag), get the index, and declares it as end of line?
しかし、どうすれば機能を継続できるのかわかりません。正直に言うと、次の行がわかりません。
dag = [badness(paragraph[i:j], page_width) + justifier(paragraph[j:], page_width) for j in range(i + 1, par_len + 1)]
そして、どのように(justifierとして戻りますか?int戻り値をリストである に格納することを既に決めているためresultです。別の関数を作成して、そこから再帰する必要がありますか? 再帰が必要ですか?
次に何をすべきかを示し、これが動的計画法である理由を説明していただけますか? 再帰がどこにあり、副問題が何であるかは本当にわかりません。
前にありがとう。