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;
}
}
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:
ReplyDeleteclass 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!