Minimum cost to reach point

Question

Given are positive integers n, a, b, p[1], p[2], p[3] (All <= 10^9). Suppose we are standing at position x=0, and we want to reach point n. We can move only to right. For 1 move, we can move by 1 at cost p[1], move by a at cost p[2] and move by b at cost p[3]. The task is to find minimum cost if we can use this moves. There is no restrictions on number of moves. The ideas I came up with are dynamic programming and linear equations with 3 variables. But still can't solve the problem.

UPD: Suppose also we are given with T (T <= 50) independent queries.

user_7836559 · Answer

Think of the last step: it would be to move right by 1 unit, a units, or b units. If the last step is to move right 1 unit, then the total cost is p[1]+mincost(n-1). Similarly for the other two possibilities.

Thus, we get the recursive equation: mincost(n) = min{p[1]+mincost(n-1), p[2]+mincost(n-a), p[3]+mincost(n-b)}. This can be implemented using top-down recursion with memoization or bottom-up dynamic programming.

user_3080723 · Answer

You mentioned that you had two ideas:

using a recurrence relation to write a dynamic programming algorithm;
solving a linear equation.

Both ideas are great. Since another answer already focuses on dynamic programming, I will focus on the linear equation.

Here is a reformulation of your problem:

MINIMIZE:
    x * p[1] + y * p[2] + z * p[3]

UNDER CONSTRAINTS:
    x + y * a + z * b = n
    x, y, z ≥ 0
    x, y, z are integers

This is an integer linear program. Formulating a problem as a linear program or as an integer linear program is a very useful skill. Congratulations!

If this is an interview question, the interviewer will probably be very happy with you simply formulating the problem as a linear program. Thus the "code" I wrote above would probably satisfy them.

There are many existing solvers for linear programs.

For instance, here is code in python, using library PuLP:

from pulp import LpProblem, LpVariable, LpMinimize

def min_cost_to_reach_point(n, a, b, p):
    x = LpVariable('x', lowBound=0, cat='Integer')
    y = LpVariable('y', lowBound=0, cat='Integer')
    z = LpVariable('z', lowBound=0, cat='Integer')
    P = LpProblem('min_cost_to_reach_point', LpMinimize)
    P += x * p[0] + y * p[1] + z * p[2]
    P += x + y * a + z * b == n
    P.solve()
    return {'cost': P.objective.value(), 'steps_1': x.value(), 'steps_a': y.value(), 'steps_b': z.value()}

n = 100
a, b = 11, 17
p = (2, 20, 20)
print( min_cost_to_reach_point(n, a, b, p) )
# {'cost': 128, 'steps_1': 4, 'steps_a': 1, 'steps_b': 5}

Minimum cost to reach point

2 Answers