hello !
I was trying to solve thisproblem but i m unable to come up with dp states . please provide some hints or thought process to solve this kind of problems.
Shrink The Array
You are given an array of positive integers A[] of length L. If Ai and Ai+1 both are equal replace them by one element with value Ai+1
. Find out the minimum possible length of the array after performing such operation any number of times.
Note:
After each such operation, the length of the array will decrease by one and elements are renumerated accordingly. Input format
The first line contains a single integer L denoting the initial length of the array A. The second line contains L space integers Ai − elements of array A[]
. Output format
Print an integer — the minimum possible length you can get after performing the operation described above any number of times. Constraints
1<=L<=500
1<=Ai<=1000
Time Limit
2 second Example Input
7 3 3 4 4 4 3 3 Output
2 Sample test case explanation
3 3 4 4 4 3 3 → 4 4 4 4 3 3 → 4 4 4 4 4 → 5 4 4 4 → 5 5 4 → 6 4. Thus the length of the array is 2.