[Need Help] Yet another DP problem!

Revision en5, by ivplay, 2017-11-30 18:13:21

Original Statement 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 need to find number of ways to pick such sub sequence in minimum move.
Examples
First line contains the integers. Second and third line contains value of low and high respectively.
(Case 0)
{2, 1, 3}
1
3
Returns: 1
The only way to choose the subset is to choose all animals.
(Case 1)
{3, 4, 1, 3, 4, 2}
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.
(Case 2)
{3, 4, 3, 1, 6, 2, 5, 7, 5, 2}
2
6
Returns: 2
(Case 3)
{3, 1, 4}
2
4
Returns: -1
(Case 4)
{2, 1, 3, 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.
(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
Returns: 3 I couldn't figure out the DP idea. Can anyone show me a direction in the problem? Thanks in advance.

Tags dynamic programming, topcoder, idea, number of ways

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)