All Tracks Algorithms Dynamic Programming 2 Dimensional Problem

Ball Elimination
Tag(s):

Algorithms, Dynamic Programming, Very-Easy

Problem
Editorial
Analytics

You have a sequence of balls. Every ball has a color. You can eliminate any single ball and pay one pound. Also you can eliminate any two neighboring balls which have the same colors for no cost.
Find minimal amount you need to spend to eliminate all balls.

Input Format:
First line contains single integer $$n$$ -- number of balls.
Second line contains $$n$$ space-separated integers $$a_1,a_2,\dots,a_n$$ -- colors of balls.

Output Format:
Single integers -- minimal cost of elimination of all balls.

Constraints:
$$1 \leqslant n \leqslant 500.$$
$$1 \leqslant a_i \leqslant 100.$$

SAMPLE INPUT
3
2 1 2
SAMPLE OUTPUT
1
Explanation

You can eliminate second ball for one pound. After that, you can eliminate remaining two balls for no price.

Time Limit: 5.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Visual Basic, Kotlin

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

HackerEarth

Challenge Name

March Clash '17

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications