10.1~10.3


シャベルが何シャベルか残っています...


濃い色の字は解答した問題だ.

  • 解決できなかった問題.
  • 917277単語混合
  • 1660隊長李多順(多順が合わない)
  • 7609回文
  • 1106ホテル
  • 225パズル(反例はまだ見つかっていません)
  • 14244ツリー
  • を作成
  • 9081単語スペル
  • 2078無限バイナリツリー

  • 復習する
  • 1939重量制限
  • 解題の跡




    考えを整理する.


    混合9177単語
    dpでもbfsでも解決できる問題知っているか分からないかのようにもっと時間を費やした.
    与えられた3文字をそれぞれw 1、w 2、w 3と呼ぶと、空の文字列からインデックスが徐々に増加し、私が追加する文字がw 3の文字と同じかどうかを確認する方法で問題を解くことができます.(うん、どう説明すればいいか)
  • dp[0][0]にTを書くのは、空の文字列が常にw 3に含まれていると仮定するためである.
  • 青色部分は、空の文字列に1文字を追加する部分、すなわちc、a、tまたはt、r、e、eであるため、直前の状態を直接インポートすることができる.
  •         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種類ある.
  • target wordの比較対象と追加する文字が異なる場合、
  • target wordの比較対象と追加する文字は同じで、
  • 左側の文字列が
  • target wordと同じ場合、
  • 右側の文字列が
  • target wordの比較対象と同じである場合、
  • はい.それぞれ書いておけばいい
    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ホテル
    問題には条件付きの費用があり、広報担当者がカウンターに入れた問題について.料金はキーで、広報担当者はアイテムで、キーが重複するとは思わなかった