룰루랄라 알고리즘

ACAYKP CAPCAK 앞의 문자열의 sub sequence를 X, 뒤의 문자열의 sub sequence를 Y라고 했을 때 문자를 하나씩 늘려가면서 비교해보자 X: A Y: C 두 문자열로 만들 수 있는 LCS의 길이는 0이다. X: A Y: CA 두 문자열로 만들 수 있는 LCS의 길이는 1이다. X: A Y: CAP 두 문자열로 만들 수 있는 LCS의 길이는 1이다. X: A Y: CAPC 두 문자열로 만들 수 있는 LCS의 길이는 1이다. 위와 같이 Y가 끝까지 CAPCAK까지 구하게 된다면 X를 하나씩 늘려주면 된다. X: AC Y: C 두 문자열로 만들 수 있는 LCS의 길이는 1이다. X: AC Y: CA 두 문자열로 만들 수 있는 LCS의 길이는 1이다. 표를 만들고 채우기 위해 값이 증가..

일반적인 바텀업 형식이 아니라 탑다운 형식의 문제

마지막을 선택해야 하고 연속해서 뽑지 못하는 수열에서 최댓값 찾기 무조건 마지막 계단 n을 밟았다고 쳤을 때 나올 수 있는 방식은 마지막 계단 전에 밟은 계단이 n-1 일 때, n-2 일 때 둘로 나뉜다 dp[i] : i번째 계단을 밟았을때 까지의 최댓값 dp[i-2] + score[i] : i번째 계단을 밟기 전에 i-2계단을 밟았을 때 dp[i-3] + score[i] + score[i-1] : i번째 계단을 밟기 전에 i-1계단을 밟았을 때 3계단을 연속으로 밟을 수 없으므로 i-2번째 계단을 밟았을 땐 i번째 점수 score[i]에 dp[i-2]를 더해 주고, i-1번째 계단을 밟았을 때는 score[i], score[i-1]에 dp[i-1-2]인 dp[i-3]을 더해 준다.

연속해서 뽑지 못하는 수열에서 최댓값 찾기 dp[i] : i번째 까지 마실 수 있는 포도주의 최댓값 dp[i-2] : i-2번째의 포도주를 마지막으로 마셨을 때 dp[i-3]+wei[i-1] : i-3번째의 포도주를 마지막으로 마셨을 때 dp[i-4]+wei[i-1] : i-4번쨰의 포도주를 마지막으로 마셨을 때 3잔을 연속해서 마시지 못하므로 dp[i-2]를 제외한 dp[i-3]과 dp[i-4]는 wei[i-1]를 더해준다

-1 : 아직 한 번도 탐색하지 않은 좌표 0 : 목표 지점까지 경로가 없는 좌표 그리고 목표 지점까지 갈 수 있는 좌표라면, 방문한 횟수에 따라 수가 올라갈 것이다. 1. dp 테이블을 -1로 초기화 한 후 dfs함수를 돌려 만약 x,y가 M-1,N-1 즉 좌표의 도착점 까지 도달한다면 1을 리턴하여 더해준다. 2. x,y의 좌표가 -1이 아니라면 방문 한 적이 있는 좌표므로 그 값을 리턴하여 더해준다. 3. 일단 좌표를 0으로 초기화 해서 4방향 dfs를 수행하여도 갈 수 있는 곳이 없다면 0을 리턴 4. 경로가 있다면 정상적으로 dfs를 수행. 5. 출발지가 결국 경로의 수가 됨 dp테이블 [3, 2, 2, 2, 1] [1, -1, -1, 1, 1] [1, -1, -1, 1, -1] [1, 1, 1..