saba_tavdgiridze's blog

DP problem.
By saba_tavdgiridze, 11 years ago, In English

Hello everybody.I'm looking at this problem and I've no idea how to solve it. It's about that,with minimum number of 1's and operations of addition, multiplication and parenthesis you must obtain positive number n.

  • Vote: I like it
  • +3
  • Vote: I do not like it

»
11 years ago, # |
  Vote: I like it +7 Vote: I do not like it

I think it can help you

So, suppose we know this minimum for all 1 <= i < n. (If n == 1, answer is 1). How can we get n? Only by addition or multiplication. So, answer[n] = minimum(answer[a] + answer[b] | a + b == n or a * b == n, a < n, b < n)

→ Reply