# [Solved] How can we develop an algorithm to solve a problem of DP [closed]

You can use DP to solve it. Here is a good website for learning DP: https://www.geeksforgeeks.org/dynamic-programming/

``````# For example X=3, Y=5, D=24. If we know solution for D=21 (24-3) and D=19 (24-5), then we know for D=24 the solution is min(D=21, D=19) +1.
# And for D=19, we know it's min(D=16, D=14) +1. So all the way back to D=3 and D=5.
def sol(X,Y,D):

# dp list for storing the solution for each D.
# For inner list, index 0 represent the usage of X, index 1 represent the usage of Y.
dp = [[float('inf'), float('inf')] for _ in range(D+1)]

# Assume X <= D and Y <= D, it guarantees both X and Y can fit in D.
# for D=X, the solution is 1X, 0Y, so it's[1,0]
dp[X] = [1,0]
# for D=Y, the solution is 0X, 1Y, so it's[0,1]
dp[Y] = [0,1]

for i in range(min(X,Y)+1, D+1):

# If already has a solution, skip.
if dp[i] != float('inf'):
continue

# Current D= min(D-X, D-Y) + 1
if sum(dp[i-X]) < sum(dp[i-Y]):
dp[i] = dp[i-X]+1
dp[i] = dp[i-X]
else:
dp[i] = dp[i-Y]
dp[i] = dp[i-Y]+1

# Search for a solution backward.
for i in range(len(dp)-1, -1, -1):
if dp[i] != float('inf') and dp[i] != float('inf'):
return (D-i, dp[i], dp[i])
return (D-i, 0, 0)

print(sol(3,5,24))
``````

Here is a simplified question for understanding DP:

``````'''
To make it easier understand, let's simplify the question: we just want to know the minimium number of tables to get to D.
For example, X=3, Y=5, D=15.
'''
def sol(X,Y,D):

# 1. We create a list of size D+1: dp = [None, None, None, ....], +1 just for easier calculation. Since the index starts at 0.
#    float('inf') represents infinity number, just for easier to use below. You will see it later.
dp = [float('inf') for _ in range(D+1)]

# 2. Our base case: when D=3, we know X=1,Y=0 is the solution, so only need 1 table to get to D=3.
#    Same for D=5: when D=5, we know X=0,Y=1 is the solution.
#    So set our base case: dp = 1, dp = 1
dp[X] = 1
dp[Y] = 1

# 4. Now the list is dp = [None, None, None, 1, None, 1, None, ....]
# 5. For D < min(X, Y), that's for sure no solution.
#    So we start calculating solution for each D > min(X,Y) (D=min(X,Y) is our base case)
for i in range(min(X,Y)+1, D+1):

# If already has a solution, skip. This is for preventing overwrite case such as Y can be formed by X.
# For example, X=3, Y=6, on dp we don't want the solution from dp[6-3].
if dp[i] != float('inf'):
continue

# 7. Let's take example at D=8. The solution could D=3 + 1 table, or D=5 + 1 table.
#    Since we want the minimum, so our solution for D=8 is: min(D-3, D-5) + 1
#    Here is the reason we initiate value is float('inf') instead of None.
#    We don't have to check if it's None before calculate.
#    For example D=7, D-3 is None, D-5 is None. min(None, None) throws error,
#    we have to check if it's None or not before calculate. But if we use float('inf'),
#    min(float('inf'), float('inf')) + 1 is still float('inf').
dp[i] = min(dp[i-X], dp[i-Y]) + 1

# 8. Search for a smallest distance solution. For D=24, there is already a solution, so return dp
#    But some D don't have solution. For example D=7 doesn't have a solution, so we check, D=6, D=5.. until
#    it finds a solution. And that's the smallest distance solution.
for i in range(len(dp)-1, -1, -1):
if dp[i] != float('inf'):
# first element is the distance, second is the number of tables.
return (D-i, dp[i])
return (D-i, 0)

print(sol(3,5,15))
``````

solved How can we develop an algorithm to solve a problem of DP [closed]