본문 바로가기

leetcode/DP

 (5)
72. Edit Distance (classic. DP problem) Given two strings word1 and word2, return the minimum number of operations required to convert word1 to word2. You have the following three operations permitted on a word: Insert a character Delete a character Replace a character Input: word1 = "horse", word2 = "ros" Output: 3 Explanation: horse -> rorse (replace 'h' with 'r') rorse -> rose (remove 'r') rose -> ros (remove 'e') 한줄요약 horse -> ros..
823. Binary Trees With Factors (python) Given an array of unique integers, arr, where each integer arr[i] is strictly greater than 1. We make a binary tree using these integers, and each number may be used for any number of times. Each non-leaf node's value should be equal to the product of the values of its children. Return the number of binary trees we can make. The answer may be too large so return the answer modulo 10^9 + 7. 한줄요약 ..
[dp]300. Longest Increasing Subsequence [python] Given an integer array nums, return the length of the longest strictly increasing subsequence. A subsequence is a sequence that can be derived from an array by deleting some or no elements without changing the order of the remaining elements. For example, [3,6,2,7] is a subsequence of the array [0,3,1,6,2,2,7]. Example 1: Input: nums = [10,9,2,5,3,7,101,18] Output: 4 Explanation: The longest inc..
[DP ]1220. Count Vowels Permutation 해설 : 이전 dp 문제들과 같이 현재 단계에서의 만들수 있는 경우의 수는 이전 단계의 a,e,i,o,u를 사용해서 만들 수 있는 경우의 합과 같다. 따라서 dp[0][0] (=a) , dp[0][1] (=e) 은 미리 구해놓고, dp[1][0] 에서는 조건들에 따라 수를 합해 나가면된다. class Solution { public: int countVowelPermutation(int n) { long long modulo = 1000000007; vector dp(n, vector (5, 0)); for(int i=0; i
[DP] 377. Combination Sum IV 377. Combination Sum 4 target 을 만들기 위한 숫자 조합 세기. target에서 1~3중에 숫자를 하나 골라서 뺏을때, 앞서 만들었던 DP를 통해서, 그 수를 만들수 있는 경우의 갯수를 더해주면 된다. DP를 저장 할 공간은 1D면 된다. 왜나면, 1을 만드는 경우의 개수, 2를 만드는 경우의 개수... 식으로 1차원만 있으면 된다. target =4 target - 고른값 target -1 = 3 -> dp[3] target -2 = 2 -> dp[2] target -3 = 1 -> dp[1] target 4를 만들 수 있는 경우의 수는 dp[3] + dp[2] + dp[1] class Solution { public: int combinationSum4(vector& nums,..

티스토리툴바