Category: dp
-
LeetCode 70: Climbing Stairs
link Dynamic Programming Subproblem Let be the number of ways to climb stairs. Then: Time: , space: .
-
LeetCode 2539: Count the Number of Good Subsequences
link Brute force Checking all substrings will take time . Observations We can use divide-and-conquer in two ways to simplify the counting problem: Count of good subsequences with instances of each char-type is thus product . We add to the count for each char type to accommodate leaving that char-type altogether from the good subsequence.…
-
LeetCode 91: Decode Ways
link Decodings can be thought of as paths in a binary tree. So, we need to count the number of paths. Note, we do not need to keep track of already counted decodings. In the example above, the first decision at the root produced two branches: (1) starts with “2” having symbol “B” (2) starts…
-
LeetCode 140: Word Break II
link Backtrack If a prefix s[0:l] is a dictionary word, we then try breaking s[l:]. Time: , space (disregarding output-size): . The solutions can be thought of as paths in a DAG. If we can construct the DAG, we can traverse the paths and collect the sentences. Dynamic Programming Subproblem Say the input string is…
-
LeetCode 1143: Longest Common Subsequence
link Dynamic Programming Subproblem Say input strings are and . Let be the length of the longest common subsequence between the pair of prefixes and . is the solution. Order Subproblems on a -grid and row-wise processing gives a topological ordering. Time: , space: . A subproblem depends on the subproblems that are on the…
-
LeetCode 647: Palindromic Substrings
link We can check if a string is a palindrome in two ways: Both ways take time. However, there is a difference: the count of possible pairs of end points is whereas the count of possible centers is . Process inwards from two ends Brute force Try all possible substrings. Time: , space: . Dynamic…
-
LeetCode 139: Word Break
link Note, word = “” + word is a valid segmentation as long as word is in wordDict. Dynamic programming Subproblem Let denote if the prefix can be broken into words. Then: Note, we assume an empty string can be segmented. Order Edges go from smaller ‘s to a bigger . Processing in the order…
-
LeetCode 39: Combination Sum
link Backtracking For each element , we take instances of it such that and try to make using other elements. We process candidates in a sorted order to be able to use a set to keep only unique combinations. Recursion tree has height and width . So, time: , space: . Dynamic programming Subproblem Let…
-
LeetCode 152: Maximum Product Subarray
link Brute force Take max of all possible subarrays. Products of all possible subarrays starting at a particular index can be computed in time. Since there are possible starting indices, total time: , space: . Dynamic programming Subproblem Without negative numbers Let be the largest product in nums[0:i+1] for a subarray that includes nums[i]. Then,…
-
LeetCode 213: House Robber II
link Dynamic Programming Sub-problem Say Rob(i) is the maximum money achievable by robbing the houses in nums[0…i]. Then: . Order The directed graph is cyclic. To break the cycle, we do two passes. First pass robs first house and thus skips the last house. Second pass skips first house. We take the maximum of these…
unreasonably effective 