伯準1149号RGB距離

1629 ワード
テキストリンク
質問リンク

この問題は長い時間をかけてやっと分かった.😫 理解してからは積み重ねが下りてきたような気がします...
これは典型的な動的計画法(DP)の問題であり,理解は難しいが,問題を理解すればコードの作成はそれほど難しくない.

問題を理解する


例を見て、簡単に問題を理解して、3つの家を赤、青、緑に塗ることができて、隣の家は同じ色に塗ることができません.[ 0]シリーズを[1],[2]の最低価格でDPリストに追加します.
[1][0]は赤色であるため、[0][1]のG(40)と[0][2]のB(83)を加算し、より小さな値をDPの[1][0]ビットに入れる.
回転for文、1番目のfor文の[1]行はi、[0]行はi-1、2番目のfor文の[2]行はi、[1]行はi-1
次のコードを見ると分かりやすいかもしれません.

コード#コード#

n = int(input())
dp = [[0]*3 for _ in range(n)]
#0으로 리셋되어있는 리스트 생성
#현재 [0,0,0], [0,0,0], [0,0,0]인 상황
house = []
#house리스트에 input받은 값 넣어 줄것임
for _ in range(n):
    house.append(list((map(int, input().split()))))
dp[0] = house[0] #dp 첫 라인은 house 첫 라인으로 픽스

for i in range(1,n): #index[1]부터니까 range1부터
#dp 두,세번째 라인 채우기
    dp[i][0] = min(dp[i-1][1],dp[i-1][2]) + house[i][0]
    dp[i][1] = min(dp[i-1][0],dp[i-1][2]) + house[i][1]
    dp[i][2] = min(dp[i-1][0],dp[i-1][1]) + house[i][2]
print(min(dp[n-1]))
理解のために2つのリストdpとhouseを添付します
print(dp)
print(house)

-> [[26, 40, 83], [89, 86, 83], [96, 172, 185]]
-> [[26, 40, 83], [49, 60, 57], [13, 89, 99]]

何でも分かったと思ったが、言葉で説明するのはあまりよくなかった.😂
歩く道は本当にとても远くてほほほ楽しいほほほ!!!
03 - Wildcards
Leetcode 102二分木レベル順序横断