The type of problem that is asking for a Dynamic Programming solution

-
The problem is this one, new one from LeetCode: https://leetcode.com/problems/number-of-longest-increasing-subsequence/description/

Given an unsorted array of integers, find the number of longest increasing subsequence.
Example 1:
Input: [1,3,5,4,7]
Output: 2
Explanation: The two longest increasing subsequence are [1, 3, 4, 7] and [1, 3, 5, 7].
Example 2:
Input: [2,2,2,2,2]
Output: 5
Explanation: The length of longest continuous increasing subsequence is 1, and there are 5 subsequences' length is 1, so output 5.
Note: Length of the given array will be not exceed 2000 and the answer is guaranteed to be fit in 32-bit signed int.
The hints that tell me that we need a Dynamic Programming (DP) solution to this problem are twofold:
1) The problem is asking for the number of sequences, but not the sequences themselves
2) Think about a brute-force approach: at each index you'd have to binary check every other previous index. That's an 2^n approach. n=2000. Intractable.
As I said before, DP never comes naturally to me, it always requires an extra effort, but I try to come up with some tools to help me arrive to a solution:
a) I know extra space will most likely be needed. I keep that in mind.
b) I ponder the problem from the following angle: suppose that I have the solution (number of longest increasing sub-sequence) for every index from 0 to i-1. Knowing that, can I derive a solution for the index i?
With that in mind, my solution was the following: have two extra arrays, one keeping track of the length of the max sub-sequence ending at the current position, and the other one keeping track of the number of max sub-sequences ending at the current position. With that, for each position i, iterate through all the previous positions and check whether you can have a max sub-sequence ending at that position, and if so update the arrays accordingly. At the end do one more linear loop to count the total number of solutions found and return it. Execution time in O(n^2), which is very reasonable for n=2000. Code is down below. And you can also see a pic of me finishing up the Beat The Blerch 10K race!!! Cheers, Marcelo.
    public class Solution
    {
        public int FindNumberOfLIS(int[] nums)
        {
            int[] maxLen = new int[nums.Length];
            int[] numMax = new int[nums.Length];
            int max = 0;

            for (int e = 0; e < nums.Length; e++)
            {
                maxLen[e] = 1;
                numMax[e] = 1;
                for (int i = 0; i < e; i++)
                {
                    if (nums[i] < nums[e] && maxLen[i] + 1 >= maxLen[e])
                    {
                        if (maxLen[i] + 1 > maxLen[e])
                        {
                            maxLen[e] = maxLen[i] + 1;
                            numMax[e] = numMax[i];
                        }
                        else
                        {
                            numMax[e] += numMax[i];
                        }
                    }
                }

                if (maxLen[e] > max)
                {
                    max = maxLen[e];
                }
            }

            int count = 0;
            for (int i = 0; i < maxLen.Length; i++)
            {
                if (maxLen[i] == max)
                {
                    count += numMax[i];
                }
            }

            return count;
        }
    }


Comments

  1. TarasNovember 25, 2017 at 8:36 PM

    Beautiful solution, Marcelo! I ended up with pretty much exactly the same solution, but in the end I decided to decouple all subproblems in code, since there are at least 2 of them - 1) finding LIS and 2) finding the number of ways to reach it. Your solution fuses them which is why in practice it performs better, but for just for fun I'm sharing here the non-fused solution:

    class Solution {
    public:
    int findNumberOfLIS(const vector& nums) {
    if (nums.empty()) return 0;
    // compute LISes
    vector lengths(nums.size(), 1);
    for (int i = 1; i < nums.size(); ++i) {
    for (int j = 0; j < i; ++j) {
    if (nums[j] < nums[i] && lengths[i] <= lengths[j]) lengths[i] = lengths[j] + 1;
    }
    }
    // tabulate number of ways to reach each length ending with nums[i]
    vector ways(nums.size());
    for (int i = 0; i < nums.size(); ++i) ways[i] = lengths[i] == 1;
    for (int i = 1; i < nums.size(); ++i) {
    for (int j = 0; j < i; ++j) {
    if ((nums[j] < nums[i]) && (lengths[j] == lengths[i] - 1)) {
    ways[i] += ways[j];
    }
    }
    }
    int longest = *max_element(lengths.cbegin(), lengths.cend());
    // sum up all the ways to reach LIS
    int total = 0;
    for (int i = 0; i < nums.size(); ++i) {
    if (lengths[i] == longest) total += ways[i];
    }
    return total;
    }
    };

    as I've said, it performs worse than your solution, but I still like it because it makes it clear that this problem actually has 2 dynamic programming subproblems :)

    Thanks for sharing this!

    ReplyDelete

Post a Comment

Popular posts from this blog

Changing the root of a binary tree

-
Image
If you work with graphics and eventually you want to pivot a binary tree using a different node as the root, this might be interesting to you. Here is the problem:  Change the Root of a Binary Tree - LeetCode 1666. Change the Root of a Binary Tree Medium 6 14 Add to List Share Given the  root  of a binary tree and a  leaf  node, reroot the tree so that the  leaf  is the new root. You can reroot the tree with the following steps for each node  cur  on the path  starting from the  leaf  up to the  root ​​​  excluding the root : If  cur  has a left child, then that child becomes  cur 's right child. Note that it is guaranteed that  cur  will have at most one child. cur 's original parent becomes  cur 's left child. Return  the new root  of the rerooted tree. Note:  Ensure that your solution sets the  Node.parent  pointers correctly after rerooting or you will receive "Wrong Answer".   Example 1: Input: root = [3,5,1,6,2,0,8,null,null,7,4], leaf = 7 Output: [7,2,nul
Read more

ProjectEuler Problem 719 (some hints, but no spoilers)

-
Image
Last time that I solved a ProjectEuler (PE) problem was in 2015... This is their latest problem as of today:  https://projecteuler.net/problem=719 Number Splitting        Problem 719 We define an  S S -number to be a natural number,  n n , that is a perfect square and its square root can be obtained by splitting the decimal representation of  n n  into 2 or more numbers then adding the numbers. For example, 81 is an  S S -number because  81 − − √ = 8 + 1 81 = 8 + 1 . 6724 is an  S S -number:  6724 − − − − √ = 6 + 72 + 4 6724 = 6 + 72 + 4 . 8281 is an  S S -number:  8281 − − − − √ = 8 + 2 + 81 = 82 + 8 + 1 8281 = 8 + 2 + 81 = 82 + 8 + 1 . 9801 is an  S S -number:  9801 − − − − √ = 98 + 0 + 1 9801 = 98 + 0 + 1 . Further we define  T ( N ) T ( N )  to be the sum of all  S S  numbers  n ≤ N n ≤ N . You are given  T ( 10 4 ) = 41333 T ( 10 4 ) = 41333 . Find  T ( 10 12 ) The rules of PE prevent me from disclosing the solution (they are very picky about it, rightfully so), but I can chat abo
Read more

Hard Leetcode Problem: Grid Illumination

-
Image
Here is the problem:  https://leetcode.com/problems/grid-illumination/ On a  N x N  grid of cells, each cell  (x, y)  with  0 <= x < N  and  0 <= y < N  has a lamp. Initially, some number of lamps are on.   lamps[i]  tells us the location of the  i -th lamp that is on.  Each lamp that is on illuminates every square on its x-axis, y-axis, and both diagonals ( similar to a Queen in chess ). For the i-th query  queries[i] = (x, y) , the answer to the query is 1 if the cell (x, y) is illuminated, else 0. After each query  (x, y)  [in the order given by  queries ], we turn off any lamps that are at cell  (x, y)  or are adjacent 8-directionally (ie., share a corner or edge with cell  (x, y) .) Return an array of answers.  Each value  answer[i]  should be equal to the answer of the  i -th query  queries[i] . Example 1: Input: N = 5 , lamps = [[0,0],[4,4]] , queries = [[1,1],[1,0]] Output: [1,0] Explanation: Before performing the first query we have both lamps [0
Read more