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

by


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][0] != float('inf'):
            continue

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

    # Search for a solution backward.
    for i in range(len(dp)-1, -1, -1):
        if dp[i][0] != float('inf') and dp[i][1] != float('inf'):
            return (D-i, dp[i][0], dp[i][1])
    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[3] = 1, dp[5] = 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[6] 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[24]
    #    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))

1

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