다이나믹프로그래밍

푼 날짜 : 2024.09.21푼 문제 : [11055] / 가장 큰 증가하는 부분 수열사용한 언어 : python알고리즘 : DP  점화식:dp[i] = max(dp[i], dp[j]+lst[i]) (if lst[j]  여기서 뽀인트🌟 는 i번째 반복이 끝날 때 현재 dp[i]와 lst[i]를 비교해서 큰 값을 넣어주는 것!안그러면 lst[i]는 0보다 큰 수 인데 dp[i]에는 0이 들어가 있게 된다. 이렇게 되면 다음 계산에 영향을 준다!!   코드 :import sysN = int(sys.stdin.readline())lst = list(map(int, sys.stdin.readline().split()))dp = [0 for _ in range(N)]dp[0] = lst[0]for i in ..

푼 날짜 : 2024.09.13푼 문제 : [1149] / RGB거리사용한 언어 : python알고리즘 : DP  점화식 :dp[i][0] = colors[i][0] + min(dp[i-1][1], dp[i-1][2]) dp[i][1] = colors[i][1] + min(dp[i-1][0], dp[i-1][2]) dp[i][2] = colors[i][2] + min(dp[i-1][0], dp[i-1][1])   초기값은 dp[0]을 colors[0]을 넣어주고 시작했다.그리고 dp테이블을 하나씩 채워나가는데, i번째의 0번째 요소를 채우기 위해서는 i-1번째의 0번이 아닌 1번과 2번 중 더 작은 값을 더해서 채워준다. 이렇게 해야 값을 최소로 만들며 더해갈 수 있기 때문이다.     코드 :impor..