Category: dp
-
LeetCode 542: 01 Matrix
link Dynamic programming For a one-cell (i, j) we can reach the nearest zero-cell via one of its four neighbors. So, if the four neighbors of the cell have already been solved, we can solve (i, j). This suggests DP. Sub-problem Order The directed graph has cycles between neighbors. We can process black arrows in…
-
LeetCode 338: Counting Bits
link Inspect binary representation Count 1’s in binary representation for each index. For a number , count_ones take time. So, the time taken to count ones for all the numbers is the sum: or time is . We use Sterling’s approximation: . So, . Time: , extra space (disregarding output): . Dynamic programming On every…
-
LeetCode 416: Partition Equal Subset Sum
link Assigning the positive numbers in two equal-sum subsets is same as creating one set having sum equal to half of the total sum. We can use Dynamic Programming. This is like coin-change except a number cannot be reused. Sub-problem Let solutions[ (i, s) ] represent the sub-problem of creating a subset with target sum…
-
LeetCode 1137: N-th Tribonacci Number
link We can use Dynamic Programming. Sub-problem solutions[i] = solutions[i-1] + solutions[i-2] + solutions[i-3] Trivial sub-problems: solutions[0], solutions[1], and solutions[2] Order Since solutions[i] only depends on solutions[j] where j < i, we can process the sub-problems in increasing order of i and that would be a topologically sorted order.
unreasonably effective 