10.1~10.3
11480 ワード
シャベルが何シャベルか残っています...
濃い色の字は解答した問題だ.
解決できなかった問題.
復習する
解題の跡
考えを整理する.
混合9177単語
dpでもbfsでも解決できる問題知っているか分からないかのようにもっと時間を費やした.
与えられた3文字をそれぞれw 1、w 2、w 3と呼ぶと、空の文字列からインデックスが徐々に増加し、私が追加する文字がw 3の文字と同じかどうかを確認する方法で問題を解くことができます.(うん、どう説明すればいいか)
dp = [[0] * (length_w2+1) for _ in range(length_w1+1)]
dp[0][0] = 1
# tree의 경우
for i in range(1,length_w2+1):
dp[0][i] = dp[0][i-1] if w2[i-1] == w3[i-1] else 0
# cat의 경우
for i in range(1,length_w1+1):
dp[i][0] = dp[i-1][0] if w1[i-1] == w3[i-1] else 0
それは上の結果と同じです.
残りの部分を見てください.
dp[1],ターゲットワードにおける現在の比較の「a」(w 3[1])
追加するオブジェクトを比較します.aはtとcに等しくありません.
target wordの比較オブジェクトと追加した文字が異なる場合はfalseを入力します.
このように繰り返すと,我々が直面している症例は全部で4種類ある.
for i in range(1,length_w1+1):
for j in range(1,length_w2+1):
if w1[i-1] != w3[i+j-1] and w2[j-1] != w3[i+j-1]:
dp[i][j] = 0
elif w1[i-1] == w3[i+j-1] and w2[j-1] == w3[i+j-1]:
dp[i][j] = 1
elif w1[i-1] == w3[i+j-1] and w2[j-1] != w3[i+j-1]:
dp[i][j] = dp[i-1][j]
elif w1[i-1] != w3[i+j-1] and w2[j-1] == w3[i+j-1]:
dp[i][j] = dp[i][j-1]
1106ホテル問題には条件付きの費用があり、広報担当者がカウンターに入れた問題について.料金はキーで、広報担当者はアイテムで、キーが重複するとは思わなかった
Reference
この問題について(10.1~10.3), 我々は、より多くの情報をここで見つけました https://velog.io/@inkyu0103/10.1テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol