Hello friends, if someone wants to help me with one task.
(I want example)

The task is:
One calculator can make two operations (multiply and subtract).
Return the minimum number of operations needed to get to target (or -1).

Example:
Your multiply number is 5
Your subtract number is 7
Your target number is 20

Starting with 1, we have:
1*5*5=25
25-7-7-7=4
4*5=20
Since we used 3 multiplications and 3 subtractions, the total amount is 6

Method
int getCount(int M, int S, int T)

Input parameters:
M - integer, the number used to multiply
S - integer, the number used to subtract
T - integer, the target number

Return value:
int, minimum number of operations needed to get to target (or -1)

I can't solve this problem because I have problem with the dynamic programming, so if anyone wants to help me (give example, or code with example...) I would be very grateful.

Thanks.

Edited 6 Years Ago by Krstevski: n/a

One calculator can make two operations (multiply and subtract).
Return the minimum number of operations needed to get to target (or -1).

Example:
Your multiply number is 5
Your subtract number is 7
Your target number is 20

Starting with 1, we have:
1*5*5=25
25-7-7-7=4
4*5=20
Since we used 3 multiplications and 3 subtractions, the total amount is 6

I can't solve this problem because I have problem with the dynamic programming

I think this is the general kind of approach you're looking for.

For your problem, try this type of approach:

  1. Use a data structure that tracks numbers and how many calculator steps it took you to get to those numbers.
  2. Start the list with just 1 (or whatever start number you want), after 0 steps.
  3. Go through the list and figure out which numbers you could get to after one calculator step.
  4. If one of those numbers is your target number, you're done.
  5. Otherwise, ignore the ones you just generated that are already in the list because you already got there in a smaller number of steps.
  6. If all of the numbers you generated are already in the list and you haven't found the target number yet, you're never going to get there; you're done.
  7. Otherwise, put the rest of the numbers in the list, with a number of steps one greater than the number you got them from.
  8. Go back to step 3.

This is just a rough pass at how you might solve the problem.

This article has been dead for over six months. Start a new discussion instead.