vsanjay_nitdgp's blog

dynamic beginner
By vsanjay_nitdgp, history, 9 years ago, In English

sir..i am dp beginner....i solved the following problem with brute-force.....but i want to know approach for DP solutions.....

pls explain the approach clearly...

thanks in advance

http://mirror.codeforces.com/problemset/problem/189/A

Tags dp
  • Vote: I like it
  • -3
  • Vote: I do not like it

Comments Comments (2)
| Write comment?
»
9 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Ok, lets calc value dp[i] — maximum number of peaces we can cut rope with length i.

How to calc it?

Let's look to last peace. It can have length a, b or c. If we know length of last peace we can reduse problem to probl with smaller i.

For example, it length of last peace is a answer equal to dp[i-a]+1.

But we can choose any of three types of peaces so we need to take best.

And we get a formula:

dp[i]=max(dp[i-a],dp[i-b],dp[i-c])+1

→ Reply