[Java/C++] Simple dp solution with explanation

• The idea is to use two arrays `len[n]` and `cnt[n]` to record the maximum length of Increasing Subsequence and the coresponding number of these sequence which ends with `nums[i]`, respectively. That is:

`len[i]`: the length of the Longest Increasing Subsequence which ends with `nums[i]`.
`cnt[i]`: the number of the Longest Increasing Subsequence which ends with `nums[i]`.

Then, the result is the sum of each `cnt[i]` while its corresponding `len[i]` is the maximum length.

Java version:

``````public int findNumberOfLIS(int[] nums) {
int n = nums.length, res = 0, max_len = 0;
int[] len =  new int[n], cnt = new int[n];
for(int i = 0; i<n; i++){
len[i] = cnt[i] = 1;
for(int j = 0; j <i ; j++){
if(nums[i] > nums[j]){
if(len[i] == len[j] + 1)cnt[i] += cnt[j];
if(len[i] < len[j] + 1){
len[i] = len[j] + 1;
cnt[i] = cnt[j];
}
}
}
if(max_len == len[i])res += cnt[i];
if(max_len < len[i]){
max_len = len[i];
res = cnt[i];
}
}
return res;
}
``````

C++ version: (use `vector<pair<int, int>> dp` to combine `len[]` and `cnt[]`)

``````    int findNumberOfLIS(vector<int>& nums) {
int n = nums.size(), res = 0, max_len = 0;
vector<pair<int,int>> dp(n,{1,1});            //dp[i]: {length, number of LIS which ends with nums[i]}
for(int i = 0; i<n; i++){
for(int j = 0; j <i ; j++){
if(nums[i] > nums[j]){
if(dp[i].first == dp[j].first + 1)dp[i].second += dp[j].second;
if(dp[i].first < dp[j].first + 1)dp[i] = {dp[j].first + 1, dp[j].second};
}
}
if(max_len == dp[i].first)res += dp[i].second;
if(max_len < dp[i].first){
max_len = dp[i].first;
res = dp[i].second;
}
}
return res;
}
``````

• This post is deleted!

• This post is deleted!

• @larrywang2014 Sorry! I modified the title.

• This post is deleted!

• @Hao-Cai said in [Java/C++] Simple dp solution with explanation:

Thanks for sharing,
one point I don't understand is that,
if(len[i] == len[j] + 1)cnt[i] += cnt[j];
why it must be the condition len[i] == len[j] + 1
I'm wondering why len[i] > len[j] doesn't work?

• @mycoy `len[i] == len[j] + 1` means that you find another subsequence with the same length of LIS which ends with `nums[i]`. While `len[i] > len[j] + 1` means that you find a subsequence, but its length is smaller compared to LIS which ends with `nums[i]`.

• @mycoy `len[i] == len[j] + 1` means that you find another subsequence with the same length of LIS which ends with `nums[i]`. While `len[i] > len[j] + 1` means that you find a subsequence, but its length is smaller compared to LIS which ends with `nums[i]`.

pretty clear! thanks!

• @Vincent-Cai
For the input sequence {1,2,3,4,5,3,4}, even though the result is correct which is 1, I was expecting cnt[6] to be equal to 1 but it is 2.

Why is cnt[5] not equal to cnt[6]? I am missing something.

Thanks.

• @jainchethan87 There are two LIS which ends with `nums[6]`, which are `[nums[0], nums[1], nums[2], nums[6]]` and `[nums[0], nums[1], nums[5], nums[6]]`. You have `nums[2] = nums[5] = 3` here.

• @Vincent-Cai
Missed it, Thanks.

• @Vincent-Cai Great idea! Python version:

``````class Solution(object):
def findNumberOfLIS(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
n=len(nums)
Len=[1]*n
Cnt=[1]*n
res=maxL=0
for i in xrange(n):
for j in xrange(i):
if nums[j]<nums[i]:
if Len[j]+1>Len[i]:
Len[i]=Len[j]+1
Cnt[i]=Cnt[j]
elif Len[j]+1==Len[i]:
Cnt[i]+=Cnt[j]
if maxL<Len[i]:
maxL=Len[i]
res=Cnt[i]
elif maxL==Len[i]:
res+=Cnt[i]
return res``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.