Scribd
Upload
26 views39 pages

DP Questions

Uploaded by

Hari Krishnan
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF or read online on Scribd
26 views39 pages

DP Questions

Uploaded by

Hari Krishnan
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF or read online on Scribd
Dynamic Programming Questions Download PDF «Dynamic Programming Questions = 5. Longest Palindromic Substring = 53. Maximum Subarray = 62. Unique Paths = 63. Unique Paths Il © 64. Minimum Path Sum = 70. Climbing Stairs = 72. Edit Distance = 121. Best Time to Buy and Sell Stock #198. House Robber = 256. Paint House = 276. Paint Fence = 303, Range Sum Query - Immutable = 338. Counting Bits = 392. Ib Subsequence = 617. Palindromic Substrings = 650.2 Keys Keyboard #87. Stone Game = 981, Minimum Falling Path Sum #1035. Uncrossed Lines = 1277. Count Square Submatrices with All Ones = 1314, Matrix Block Sum = 1326, Minimum Number of Taps to Open to Water a Garden = 1335, Minimum Difficulty of a Job Schedule #1458. Max Dot Product of Two Subsequences = 1473. Paint House IIT = 1478. Allocate Mailboxes 5. Longest Palindromic Substring Description Given a string s, find the longest palindromic substring in s. You may assune ‘that the maximum length of s is 1000, Example 1: Input: “babad" Output: "bab" Note: "aba" is also a valid answer. Example 2: Input: "cbbd" Output: "bb" Solution 01/13/2020 (Dynamic Programming): class Solution { public: string longestPalindrome(string s) { int n= [Link](), start, max_len = 0; if (n ) return " vector> dp(n, vector(n, false)); for (int i= 0; i< nj; ++i) dpli}li] = true; for (int i i= 0; —i) { for (int j= i+ 2; j< ny +4) ¢ dp(il{j] = dpli + Uj - 11 §6 stil oa 3 for (int i i maxten) { max_ten = j - i +1; sli+ iy s(jli return [Link](start, max_len); 01/13/2020 (Expand Around Center): class Solution ¢ public: string longestPalindrome(string s) { int n = [Link](), start = 0, maxten=n>071: for(int i= 0; i< nj +i) { for (int l= 4-1, r= 1; 1>= 0 8&r maxten) { maxlen= 1 -1+1; strl; —-l, +r) ¢ for (int 1 = i - Feisd; lo 086 ren Sh sll = sir]; 1 He) if (r - U+ 1 > max_len) { max_len= 1-14]; start } } } return max_len + s-substr(start, max_ten) j 53. Maximum Subarray Description Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum. Example: Input: [-2,1,-3,4,-1,2,1,-5,41, Output: 6 Explanation: [4,-1,2,1] has the largest sum = 6. Follow up: If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle. Solution 01/13/2020 (Dynamic Programming): class Solution { public: int maxSubArray|vector& nuns) { int n = [Link](), max_sum = nums (0); for (int i if (nums{i - 1] > 0) nums{i] += nums fi - 11; max_sum = max(nax_sum, nums(i}); } return max_sun; pai Right -> Down 2. Right —> Down -> Right 3. Down -> Right -> Right Example Input: m Output: 28 Solution 01/29/2020: class Solution { public: int uniquePaths|int m, int n) { vectorsvector> dp(m + 1, vector(n + 1, 0))5 dptel [il for (int i i Right -> Down -> Down 2. Down -> Down -> Right -> Right Solution 01/27/2020: class Solution { public: int uniquePathsWithObstacles(vectorsvectorsinta2& obstacleGrid) { -a! 71: 21 int m = [Link](), n = obstacleGrid|0] .size(); if (m I[ 1 == @) return vector> dp(m, vector(n, @)); opie (01 = obstacleGridiol [0] == 170: 1; // OpLil [j] the total number of unique noves If Op (il (31 = dpli = 104] * (gradi - WG] != 1) + aplal ly - 11 * (grid [i] v for (int i i= 0) dplillj] += oplillj - 1] = (obstacteGrid {il [j - 1] 10); } + return (m- 1>=@ && n-1 >= 0) ? dplm- 1] [n - 1] : a; 64. Minimum Path Sum Description Given am xn grid filled with non-negative nunbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path. Note: You can only move either down or right at any point in time, Example: Input: t (1,3,1], (5,11, (42,01 1 Output: 7 Explanation: Because the path 1+3+1+1+1 minimizes the sun. Solution 01/27/2020; class Solution { public: int minPathSum(vectorsvectorsint>>6 grid) { ant m = [Link](), n = grid[0].size(): if (m= 0 || n == @) return 0; const int INF = 19 + 5; vector> dp(m, vector(n, INF)); ple] [0] = grid {ol fol; // oplil [J]: the minimum sum from grid [9] [0] to gridfi][j] // oplil Gj] = min(apli - 11{j], éplal{j - 11) + griafil fj for (int i i= 0) dplillj) = min(gridfil lj] + dpli - 1161, dplil G1): if (j - 1 >= 0) dplil fj] = min(gridfil (j] + opti) (j - 11, dp lil G15 + } return dplm ~ 1] In - 1); + 70. Climbing Stairs Description You are climbing a stair case. It takes n steps to reach to the top. Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top? Note: Given n will be a positive integer. Example 1: Input: 2 Output: 2 Explanation: There are two ways to climb to the top. 1. 1 step +1 step 2. 2 steps Example 2: Input: 3 output: 3 Explanation: There are three ways to climb to the top. 1. 1 step +1 step +1 step 2. 1 step + 2 steps 3, 2 steps + 1 step Solution 01/14/2020 (Dynamic Programming): class Solution ¢ public: int climbStairs(int n) { int s1 = 1, 52 = 2 for (int i= 2; i= 27? 52: $1; + h 72. Edit Distance Description Given two words word] and word2, find the minimum nunber of operations required to convert word1 to word2. You have the following 3 operations permitted on a word: Insert a character Delete @ character Replace a character Example 1: Input: wordl = "horse", word2 = "ros" Output: 3 Explanation: horse -> rorse (replace *h' with 'r*) rorse -> rose (renove 'r') rose -> ros (remove 'e') Example 2: Input: word) = execution" output: 5 Explanation: intention -> inention (remove 't') inention -> enention (replace ‘it with ‘e') enention -> exention (replace ‘n' with *x') exention -> exection (replace 'n' with 'c') exection > execution (insert 'u'] intention", word2 = Solution 01/27/2020: class Solution { public: int minDistance(string word1, string word2) { int m = [Link](), n = [Link](); if (m= 0) return nz if (n == @) return m; const int INF = 1e9 + 5; vectorevector> dp(m + 1, vector(n + 1, INF)); dplol [0] = 0; // oplil til the edit distance between wordi[0..i] and word2(@..j] // oplil lil = dpli - UU - 1) if word1[i] == word2[j]: no operations needed V/ Oplil Lj] = mint if word1 [i] != word2[j] i dpli = 15 = 11 +1, replace word1 li] by word? [J] //- dpli - 1[j] +1, delete character word1[i] //- dpliltj - +2 delete character word2[j] wy ++i) dpi] [0] ++i) dpe] [4] +i) { ei) word2[j - 11) { dpli - 1](0] + 1; dplol {i - 1] + 1; for (int for (int i for (int i for (int j ti Af (wordi[i - 1] dp (il (j] = dpli - 1115 - 11: } else { dp (il [5] = min(dp{i - 1) [Jj], min(dplillj - 11, dpli - 1(j - 1)) + 45 y y } return dpm] [n]; + 121. Best Time to Buy and Sell Stock Description Say you have an array for which the ith elenent is the price of a given stock on day i. If you were only permitted to complete at most one transaction (i.e., buy one and sell one share of the stock), design an algorithm to find the maximum profit. Note that you cannot sell a stock before you buy one. Example 1: Input: [7,1,5,3,6,4] Output: 5 Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 1=5. Not 7-1 = 6, as selling price needs to be larger then buying price. Example 2: Input: (7,6,4,3,1] output: @ Explanation: In this case, no transaction is done, i.e. max profit = 0, Solution 01/13/2020 (Dynamic Programming): class Solution { publics int maxProfit(vector& prices) { int n = [Link](); if (n <= 1) return @; vectoreint> diffin - 1, 0) for (int i i 0) diffli] max_sum = max(diff[i], max_sum); } return max_sun; diff li - 1; 198. House Robber Description You ere a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you fron robbing each of them is that adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night. Given a List of non-negative integers representing the anount of money of each house, determine the maximum anount of money you can rob tonight without alerting the police. Example 1: Input: [1,2,3,1] Output: 4 Explanation: Rob house 1 (money = 1) and then rob house 3 (noney = 3). Total amount you can rob = 1+3= 4, Example 2: Input: [2,7,9,3,1] Output: 12 Explanation: Rob house 1 (money = 2), rob house 3 (money = 9) and rob house 5 (money = 1). Total amount you can rob =2+9+1= 12. Solution 01/14/2020 (Dynamic Programming): class Solution { public: int rob(vector& nums) { if ([Link]|) >= 2) nums(1] = max(nums (0), nums{1J); for (int i= 2; i < [Link]); ++i) ums [i] = max(nuns fi - 11, nums{i - 21 + nums(il); return [Link]() > @ ? [Link]() : + a 256. Paint House Description There are a row of n houses, each house can be painted with one of the three colors: red, blue or green. The cost of painting each house with a certain color is different. You have to paint all the houses such that no two adjacent houses have the sane color. The cost of painting each house with a certain color is represented by an x 3 cost matrix. For example, costs(@][0] is the cost of painting house @ with color red; costs{1] [2] is the cost of painting house 1 with color green, and so on... Find the minimum cost to paint all houses. Note: ALL costs are positive integers. Example: Input: [[17,2,171, [16, 16,51, (14,3,191] Output: 10 Explanation: Paint house @ into blue, paint house 1 into green, paint house 2 into blue. Minimum cost: 2 +5 + 3= 10. Solution 05/26/2020; class Solution { public: int minCost (vector>& costs) { if ([Link]()) return 0; int n = [Link](); for (int i 0 ? *min_element([Link]() -begin(), [Link]() -end()) : 03 + 276. Paint Fence Description There is a fence with n posts, each post can be painted with one of the k colors. You have to paint all the posts such that no more than two adjacent fence posts have the sane color. Return the total number of ways you can paint the fence. Note: n and k are non-negative integers. Example: Input: n=3, k=2 Output: 6 Explanation: Take cl as color 1, 2 as color 2. All possible ways are: post1 post? post? 1 a od 2 a oa oa 3 cae 4 2 ad oa 5 2 cal 6 2 2 a Solution 01/14/2020 (Dynamic Programming): class Solution { public: int numWays(int n, int k) { if (n = 0 || k == @) return 0; vectorevector> dp(n, vector(2, 0)); plo] Lo) = k; for (int i= paisns ra ¢ dplillol = (dpli - 11(0] + dpli - (11) * tk - 1; dplil(1] = dpli - 11[0]; } return [Link]() [0] + [Link]() [1]; + hi 01/14/2020: (Dynamic Programming, Improve Space Complexity): class Solution { public: int numbays(int n, int k) { if (n = 0 || k == @) return 0; vector dp(2, 0); ple) = ks for (int i= 1) i 1 sumRange(2, 5) —> -2 sumRange(@, 5) -> -3 Note: You may assume that the array does not change. There are many calls to sumRange function. Solution 01/14/2020 (Dynamic Programming): class NumArray { public: vector num: NunArray(vector& nums) { for (int i i <[Link](); ++i) nums{i] += nums{i - 1]; this-snums = nums; int sumRange(int i, int j) { return 1 > @ 7 nums{j] - numsia - 1] : nums (J); + fee * Your Numirray object will be instantiated and called as such: * NumArrays obj = new NumArray(nums); * int param_1 = obj->sumRange( i, j); ” 338. Counting Bits Deseription Given anon negative integer number num. For every numbers i in the range 0 < i < num calculate the number of 1's in their binary representation and return them as an array. Example 1: Input: 2 Output: (0,1, 1] Example 2: Input: 5 Output: [0,1,1,2,1,2] Follow up: It is very easy to come up with a solution with run time O(n*sizeof(integer)). But can you do it in linear time 0(n) /possibly in a single pass? Space complexity should be O(n). Can you do it Like a boss? Do it without using any builtin function Like __builtin_popcount in c++ or in any other language. Solution 01/15/2020 (Dynamic Programming): class Solution { public: vector countBits(int nun) { vectorsint> dp(num +1, 0); for (int i= 1, , m= 1; i <= num; ++i) { if (Gsem<= 18, and you want to check one by one to see if T has its subsequence. In this scenario, how woule you change your code? Credits: Special thanks to @pbrother for adding this problem and creating all test cases. Solution 01/14/2020 (Dynamic Programming, Memory Limit Fuceeded): class Solution { public: bool isSubsequence(string s, string t) { if ([Link]() >= [Link]()) return s == ti return [Link]|) == t-back() ? isSubsequence([Link](@, [Link]() - 1), tisubstr(0, [Link]() - 1)) : isSubsequence(s, [Link](@, [Link]() - 1)); 01/14/2020 (Dynamic Programming (bottom-up), Two pointers): class Solution { public: bool isSubsequence(string s, string t) < int ps = 0, pt = 0; for (; ps < sisize() && pt < [Link](); +pt) if (sips) == tiptl) ++ps; return ps == [Link](); + 647. Palindromic Substrings Description Given a string, your task is to count how many palindromic substrings in this string. The substrings with different start indexes or end indexes are counted as different substrings even they consist of same characters. Example 1: Input: "abc" output: 3 Explanation: Three palindromic string: Example 2: Input: “aaa! output: 6 Explanation: Six palindromic strings: "a", "a", , "aa", Maat, “aaa! Note: The input string length won't exceed 1000. Solution 01/15/2020 (Expand Around Center): class Solution { public: int countSubstrings(string s) { int ret for (int i for (int L= i, 6 +ret; for (int l= i, r= i+ 1; 1>= 0 6&r <[Link]() && s[Ul Her) Heret; } i <[Link](); ++i) ( L>= 0 8 F< [Link]) 6 sill s{rlz --U, +r) sirl; - return ret; + Description Initially on a notepad only one character * 650. 2 Keys Keyboard Is present. You can perform two operations on this notepad for each step: Copy All: You can copy all the characters present on the notepad (partial copy is not allowed). Paste: You can paste the characters which are copied last time. Given a number n. You have to get exactly n on the notepad by performing the mininum number of steps permitted. Output the minimum nunber of steps to get n "aN Example 1: Input: 3 output: 3 Explanation: Intitally, In step 1, In step 2, In step 3, Note: The n will be have one character 'A' use Copy ALL operation. use Paste operation to get ‘AA' use Paste operation to get ‘AAA’. in the range [1, 1000]. Solution 06/09/2020: class Solution { public: int minSteps(int n) { // oplil: the minimum steps to obtain i A's // oplil = min_j(dp(j] + 1+ li - 5) / 5) min_j(dp(j] + i / i) vector dp(n + 1, INT_MAX); min_j(dpljl +1+i/ 5-1) = dpi) = 0; for (ant i= 25 i <= ny #44) for (int j = 1; j < i; +9) if (itsj @) dpli] = min(dplil, dplj] +i / 4); return dp[a); + 877. Stone Game Description Alex and Lee play a game with piles of stones. There are an even number of piles arranged in a row, and each pile has a positive integer number of stones piles (il. The objective of the game is to end with the most stones. stones is odd, so there are no ties. Alex and Lee take turns, with Alex starting first. the entire pile of stones from either the beginning or the end of the row. The total number of Each turn, a player takes This continues until there are no more piles left, at which point the person with the most stones wins. Assuming Alex and Lee play optimally, return True if and only if Alex wins the game. Example 1: Input: (5,3,4,5] Output: true Explanation: Alex starts first, and can only take the first 5 or the last 5. Say he takes the first 5, so that the row becones [3, 4, 5]. It Lee takes 3, then the board is [4, 5], and Alex takes 5 to win with 10 points. If Lee takes the last 5, then the board is (3, 4], and Alex takes 4 to win with 9 points. This demonstrated that taking the first 5 was a winning move for Alex, so we return true. Note: 2 = [Link] <= 500 piles. length is even. 1 <= piles[i] <= 500 sum(piles) is odd. Solution 01/15/2020 (Mathematics): class Solution { public: bool stoneGane(vector& piles) { 7/ opLillil: the largest number of stones Alex can pick int n = [Link](): vector> dp(n, vector>& A) { int n= A[0].size(), K = 1; Af (n == 0) return 0; // oplil [j]: the current smallest sum from row @ to row i at column j. vectorevector> dp(n, vector> dp(m, vector(n, 0)); for (int i= 0; i 0 && j > 0) dplil(j] = dplil lj] + dpli - 1115 - 115 if (4 > 0) dplilLj] = maxidplil (31, dpli - 11); 4f (j > 0) dplallj) = maxidplil 5], dplil lj - 115 y } return [Link]().back(); 1277. Count Square Submatrices with All Ones Description Given am ¥ n matrix of ones and zeros, return how many square submatrices have all ones. Example 1: Input: matrix = l (0,1,1,11, (1,1,1,11, (0,1,1,1) J Output: 15 Explanation: There are 10 squares of side 1 There are 4 squares of side 2. There is 1 square of side 3. Total number of squares = 10 +4+1= 15. Example 2: Input: matrix = t (10,11, (1,1,¢, (1,1,¢1 1 Output: 7 Explanation: There are 6 squares of side 1. There is 1 square of side 2. Total number of squares = 6 +1 = 7. Constraints: 1 <= arr. length < 300 1 <= arr[0]. length 0 <= arrlillj] <= 1 300 Solution (01/14/2020 (Dynamic Programming): class Solution { public: int countSquares (vector>& matrix) { ant m = [Link](), n = matrix(o).size(), ret = vector dp(n, vector> matrixBlockSum(vector>& mat, int K) { int m= [Link](), n = mat{o].size(); vectorevectorcint>> ret(m, vector(n, 0)): for (int i i= OGG i tk > matrixBlocksum(vectorcvector>S mat, int K) { int m= [Link](), n = mat{@].size(); vectorsvector> dp(m, vector(n, 0)); vector> ret(m, vector(n, 0); dp(e] [0] = mat lo] [0]; for (int 4 = 1; 1. 0) retlillj] -= dplra - 1[c2l; if (c1 > 0) retlil(j] -= dplr2) {ct - 11; if (r1 > 0 8 cl > 0) retlil[j] += dplra - 1fc1 - 11; } } return ret; y 1326. Minimum Number of Taps to Open to Water a Garden Description There is a one-dinensional garden on the x-axis. The garden starts at the point © and ends at the point n. (ise The length of the garden is n). There are n+ 1 taps located at points [0, 1, ..., n] in the garden. Given an integer n and an integer array ranges of length n + 1 where ranges[il (0-indexed) means the i-th tap can water the area [i - ranges[il, i + ranges[il] if it was open. Return the minimum number of taps that should be open to water the whole garden, If the garden cannot be watered return -1. Example 1: Input: n= 5, ranges = [3,4,1,1,0,0] Output: 1 Explanation: The tap at point @ can cover the interval [-3,3] The tap at point 1 can cover the interval [-3,5] The tap at point 2 can cover the interval [1,3] The tap at point 3 can cover the interval [2,4] The tap at point 4 can cover the interval [4,4] The tap at point 5 cen cover the interval [5,51 Opening Only the second tap will water the whole garden [0,51 Example 2: Input: n = 3, ranges = [0,0,0,01 Output: -2 Explanation: Even if you activate all the four taps you cannot water the whole garden. Example Input: n= Output: 3 Example 4: ranges (1,2,1,0,2,1,0,11 Input: n= 8, ranges = [4,0,0,0,0,0,0,0,4) 2 outpu: Example Input: n Output: 1 8, ranges = [4,0,0,0,4,0,0,0,4) Constraints: lene 4 ranges. length == a +1 © <= ranges[i] <= 100 Solution 01/19/2020 (Dynamic Programming): const int INF = 1e9 + 5; class Solution { public: int minTaps(int n, vectorsint>6 ranges) { vectorspaircint, int>> intervals; for (int i min(i + ranges[i], n)}); // oplil: the minimum number of taps cover from @ to point 1 int best = INF; vectorsint> dp(n + 1, INF): for (int i= 0; i <= nj +i) { if (intervals li]. first <= 0) dplil for (int j= 4+ 4; J dp(n + 1, INF); for (int i& jobDifficulty, int d) { int n = [Link](); if (n> diff(n, vector(n, 0)); J/ GiFFLA1 Lj]: max diff from jobDifficultyli] to jobdifficultylj] for (int i= 0; i > dp(n, vector(d, INF)); for (int j j& nums1, vectorcint>& nums2) { // éplil{j]: the maximun dot product of two subsequences // oums1(0..i], nums2(0.. J]; // oplil (31 = max(max(@, numsi{i] * nums2{j1) + opi - 1Lj - 11, dpli - U1 U1, dpi - an int nl = [Link](), n2 = [Link](): vector> dp(n1, vector(n2, INT_MIN)); dp (e] (0) = nunsi() * nums2(0]; for (int 4 = 1; 1 < mij ++1) dpli) {0} = max(numsi(1) * nums2(e), dpl ~ 1) (01): for (int j = 1; j < m2; +4j) dplel(j] = max(numsi(0] * nums2{j], dp lO] [j - uy for (int i i& nums1, vector& nums2) { int n1 = [Link](), n2 = [Link](); vectorevector> dp(n1, vector(n2)); for (int i= i © & j >) dplillj] = max(dplil{j], max(nuns1{i] * nums2[j], 0) + dpli - 1G - 15 if (i > 0) dplil(j] = max(dplil (1, dpa - 11041)5 if (j > 0) dplil{j] = maxidplil (j], dplil lj - 11); ¥ } return dpind - 1J{n2 - 1]; y h 1473. Paint House III Description There is a row of m houses in a small city, each house must be painted with one of the n colors (labeled from 1 to n), some houses that has been painted last summer should not be painted again. A neighborhood is a maximal group of continuous houses that are painted with the same color. (For example: houses = [1,2,2,3,3,2,1,1] contains 5 neighborhoods (ay, 42,2), 43,3}, 42}, (4,141). Given an array houses, an m * a matrix cost and an integer target where: houses lil: is the color of the house i, 0 if the house is not painted yet. cost li] lj]: is the cost of paint the house i with the color jt. Return the minimun cost of painting all the remaining houses in such a way that ‘there are exactly target neighborhoods, if not possible return -1. Example 1: Input: houses n= 2, target Output: 9 Explanation: Paint houses of this way [1,2,2,1,1] This array contains target = 3 neighborhoods, [{1}, {2,2h, {1,1}]. Cost of paint all houses (1+1+1+1+5) =9. Example 2: [0,0,0,0,01, cost = [[1,10], [10,1], (10,11, [1,10], [5,11], m = 5, 3 Input: houses n= 2, target output: 12 Explanation: Some houses are already painted, Paint the houses of this way (2,2,1,2,21 This array contains target = 3 neighborhoods, [{2,2), {1}, (2,23. Cost of paint the first and last house (10 + 1) = 11. Example 3: (0,2,1,2,01, cost = {[1,10], [10,1], (10,11, (1,10), [5,11], m= 5, 3 Input: houses n= 2, target output: 5 Example 4: [0,0,0,2,0], cost = [[1,10], (10,1), (1,10), [10,1], [1,101], m= 5, 5 Input: houses 3, target = 3 Output: ~ (3,1,2,3], cost = [[1,1,1],[1,1,1], (1,1,11,[1,1,11], m= 4, n Explanation: Houses are already painted with a total of 4 neighborhoods [{3}, {1},42},43H different of target = 3. Constraints: houses. length == cost. length cost [i]. length m <= 100 n= 2 target <= m houses{i} <= n cost [i] [j] <= 10-4 Solution 06/06/2020: int dp [101] [101] [20]; class Solution { public: int minCost(vector& houses, vector>& cost, int m, int n, int target) { fiUL_n(dp [0] [0], 101 ¥ 101 + 20, INT_MAX); filL_n(dp(0l [0], 20, 0); for (int i <= mj Hi) { int hi = housesli - 1] - 1; for (int k = 1; k <= target; +k) { for (int j = 0; j & houses, vector>& cost, int m, int n, int target) { for (int k = 0; k <= target; +k) for (int i i<= mj +4) for (int j = 0; j <5 +4) dp Lil [j] [k] = INTMAK; for (int j j & v, int n, int k) { if (n == 0) return 0; if (k == 0) return 169; if (dplnl [kl ) return dpin] (kl; int ret = 1e9; for (int take = 1; take <= n; ++take) { ant rhs =n - 1; int Uns = rhs — take + 1; int mid = (Uns + rhs) / 2; int candidate for (int i= Uns; i <= rhs; +i) { cendidate += abs(vimid) ~ vlil); y ret = min(ret, candidate + solve(v, n - take, k - 1)); } pin} [k] = ret; return ret + class Solution { public: int minDistance|vectoreint>& houses, int k) { memset (dp, ~1, sizeof(dp)); sort([Link](), [Link]()); return solve(houses, [Link](), k);

You might also like