Yet another DP problem!
Difference between en1 and en2, changed 283 character(s)
https://community.topcoder.com/stat?c=problem_statement&pm=13268&rd=16187    ↵
Problem Summary : Given an array of 1<=N<=47 integers. All the integers are in range [1,47]. Given two number low,high(1<=low<=high<=47). We have pick a sub sequence of the given array in **minimum move** that contains only the numbers in range [low,high] and all the numbers in range[low,high]. In a single move we can pick a continuous sequence of numbers from the given array. We to find number of ways to pick such sub sequence in minimum move.    ↵
Examples

0) ↵
 
    ↵
First line contains the integers. Second and third line contains value of low and high respectively.    ↵
(Case 0)
     
{2, 1, 3}

1↵
3
    ↵
1    ↵
3     

Returns: 1
    
The only way to choose the subset is to choose all animals.

1) ↵
    ↵
(Case 1)
    
{3, 4, 1, 3, 4, 2}

1↵
3
    ↵
1    ↵
3        

Returns: 2
    
In the optimal solution we send away animals #2, #3, and #5 (0-based indices). Animals #2 and #3 form one group, 
    animal #5 forms the other.
2) ↵
    ↵
(Case 2)
    
{3, 4, 3, 1, 6, 2, 5, 7, 5, 2}

2↵
6↵
Returns: 2↵
3) ↵
    ↵
2    ↵
6    ↵
Returns: 2    ↵
(Case 3)
    
{3, 1, 4}

2↵
4↵
Returns: -1↵
4) ↵
    ↵
2    ↵
4    ↵
Returns: -1    ↵
(Case 4)
    
{2, 1, 3, 1, 4}

1↵
4
    ↵
1    ↵
4    

Returns: 1
    
Note that we are not required to minimize the number of animals we send. Here, we could select just four of these five animals but that would create two groups. A better solution is to select all five animals, then they all form a single group.

5) ↵
    ↵
(Case 5)
    
{7, 12, 2, 12, 10, 13, 6, 5, 3, 3, 4, 11, 12, 4, 3, 1, 8, 11, 4, 7, 6, 5, 47}

2↵
7
    ↵
2    ↵
7    

Returns: 3    Don't figure out the DP idea. Can anyone show me a direction in the problem? Thanks in advance. 

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en5 English ivplay 2017-11-30 18:13:21 8 Tiny change: 'rns: 3 Don't figure' -> 'rns: 3 I couldn't figure'
en4 English ivplay 2017-11-30 18:11:41 5 Tiny change: 'array. We to find n' -> 'array. We need to find n'
en3 English ivplay 2017-11-30 18:10:26 34 Tiny change: 'https://co' -> 'Original Statement https://co'
en2 English ivplay 2017-11-30 18:09:42 283
en1 English ivplay 2017-11-30 18:04:54 1463 Initial revision (published)