본문 바로가기
반응형

DP40

[leetcode] 115. Distinct Subsequences 문제 : https://leetcode.com/problems/distinct-subsequences/ 문자열 s, t가 주어지면 t와 동일한 s의 고유한 하위 시퀀스 수를 반환하라. 답은 32비트 부호있는 정수임을 보장한다. DP로 풀었다. dp[i][j] = t[0~j]와 동일한 s[0~i]의 고유한 하위 시퀀스 수. dp[i][j] = dp[i-1][j] + dp[i-1][j-1] (s[i]가 t[j]인 경우) dp[i][j] (s[i] 가 t[j]가 아닌 경우) 점화식은 위와 같다. s[i] == t[j]인 경우 s[0~i-1] 문자열의 고유 하위 시퀀스들 문자 뒤에 s[i]를 붙이면 t[0~j]가 되므로 dp[i-1][j]에 dp[i-1][j-1]을 더해준다. ex) s = "rabbbit", .. 2021. 9. 19.
[leetcode] 446. Arithmetic Slices II - Subsequence 문제 : https://leetcode.com/problems/arithmetic-slices-ii-subsequence/ 정수 배열 nums가 주어지면 모든 arithmetic subsequences 의 수를 구하라. 시퀀스들의 숫자가 3개 이상이고 연속되는 두 요소의 차이가 동일한 경우 arithmetic subsequences라 한다. i:j->(j-i)가 차이이고 i, j를 포함하는 subsequences 수 (i>j) 4:2->1 [4,2] 6:2->1 [6,2] 6:4->2 [6,4,2] [6,4] 8:2->1 [8,2] 8:4->1 [8,4] 8:6->3 [8,6,4,2] [8,6,4] [8,6] 10:2->1 [10,2] 10:4->1 [10,4] 10:6->2 [10,6,2] [10,6].. 2021. 9. 11.
[leetcode] 132. Palindrome Partitioning II 문제 : https://leetcode.com/problems/palindrome-partitioning-ii/ 문자열 s가 주어지면 s를 잘라 부분문자열들을 만들었을 때 모든 부분문자열들이 펠린드롬이 되는 최소 절단횟수를 구하여라. 먼저 DP로 2차원 배열을 만들어 펠린드롬[i][e] = 문자열[i,e]가 펠린드롬인지를 구한다. 펠린드롬[i][j] = 펠린드롬[i+1][j-1] (s[i] == s[j]) = false (s[i] != s[j]) 문자열[i~j]은 문자열의 첫문자와 끝 문자가 다르면 false, 첫문자와 끝문자가 같다면 문자열[i+1, e-1]이 펠린드롬인 경우는 펠린드롬, 아니면 펠린드롬이 아니다. 위 점화식으로 펠린드롬 여부를 구하면 이번엔 1차원 배열을 만든다. dp[i] = s[0.. 2021. 8. 7.
[leetcode] 639. Decode Ways II 문제 : https://leetcode.com/problems/decode-ways-ii/ A ~ Z 문자가 1 ~ 26 숫자로 인코딩된다.(01, 02 는 1, 2와 다르다.) 숫자와 * 문자로 이루어진 문자열이 주어진다. * 문자는 0을 제외한 1~9로 대체할 수 있다. 입력 문자열을 디코딩하였을 때 만들 수 있는 문자열들의 경우의 수를 구해라. 백트래킹과 DP(memoization)을 이용해서 풀었다. dp[ind] = 입력문자열[ind~]로 만들 수 있는 정답 경우의 수 ind 번째 문자를 탐색 중일 때, 해당 문자는 십의자리로 디코딩될수도 있고, 일의자리로 디코딩 될 수도 있다. 두 가지 경우의 수를 구한뒤 더해준다. 십의 자리로 디코딩될 수 있는 경우의 수를 먼저 알아보자. 만일 ind+1 번.. 2021. 7. 14.
[Leetcode][576] Out of Boundary Paths 문제 : https://leetcode.com/problems/out-of-boundary-paths/ DP. 메모이제이션이 필요하다. 남은 maxCount 횟수, 현재 좌표가 같다면 정답 횟수는 같아진다. 즉, dp[maxCount][row][column] = 경계를 벗어나는 경로 횟수 를 저장한다. dp[maxCount][row][column] = dp[maxCount-1][row][column+1] + dp[maxCount-1][row][column-1] + dp[maxCount-1][row+1][column] + dp[maxCount-1][row-1][column] 이동은 상하좌우로 할 수 있기 때문에 점화식은 다음과 같다. 더한 값에 1000000007을 나눈 나머지값을 저장해줘야한다. 만일 r.. 2021. 6. 25.
[Programmers] N으로 표현 문제 : https://programmers.co.kr/learn/courses/30/lessons/42895 DP 관련 문제이니 DP로 풀어야겠는데 number를 인덱스로 dp 배열을 만드려고하니 막막하다. 막힐때는 제한사항을 보면서 문제 제작자의 의도를 파악해보자. 제한사항 1. 1 2021. 6. 8.
반응형

티스토리툴바