Dynamic Programming Problems

Q1. Find the subset of numbers from a list which sum up to N.

Ans:

def subset_sum(M, nums):
    
    DP = [[False for _ in range(M+1)] for _ in range(len(nums)+1)]
    
    #Initialize the first row and colum to be True
    for i in range(len(nums)+1):
        DP[i][0] = True
    
    #Construct the rest of the table
 
    for i in range(1, len(nums)+1):
        for j in range(1, M+1):
                
            if j < nums[i-1]:   # if local sum value is less than the previous item
                DP[i][j] = DP[i-1][j]  # Don't include the item
                
            else:  # if local sum value is not less than the previous item
                if DP[i-1][j]:  # If previous cell value is True
                    DP[i][j] = DP[i-1][j]
                else:
                    DP[i][j] = DP[i-1][j-nums[i-1]]

    # Get the subset values which sum upto the desired sum.
    j = M
    i = len(nums)
    while i > 0 or j > 0:

        if DP[i][j] == DP[i-1][j]:  # If current cell item is same as above cell item. 
            i = i-1
        else:
            print('item for the subset: %d' % nums[i - 1])
            j = j-nums[i-1]  # Decrement the column index by actual integer, and decrement the row index by 1.
            i = i-1
        
                
M = 12
nums = [1, 2, 4, 6]

subset_sum(M, nums)

Q2. Find the longest common subsequence between two strings.

Ans:

def longest_common_subseq(s1, s2):
    
    DP = [[0 for _ in range(len(s1)+1)] for _ in range(len(s2)+1)]

    for i in range(len(s1)):
        DP[i][0] = 0

    # Construct the table
    for i in range(1, len(s1)+1):
        for j in range(1, len(s2)+1):
            
            if s1[i-1] == s2[j-1]: # if chars are matching
                DP[i][j] = DP[i-1][j-1]+1
            else:  
                DP[i][j] = max(DP[i-1][j], DP[i][j-1])
                
    # Retrieve the longest common subsequence
    lcs = ''
    i, j = len(s1), len(s2)
    
    while i > 0 or j > 0:
        if s1[i-1] == s2[j-1]:  # if chars are matching then char is part of lcs
            lcs += s1[i-1]
            
            # Got to diagonal cell
            i -= 1
            j -= 1
        
        # if chars are not matching then find larger of 2 cells and go one step in direction of larger one
        elif DP[i-1][j] > DP[i][j-1]:  # top cell value > left cell value 
            i -= 1  # go up
        else:  # left cell value > top cell value 
            
            j -= 1  # go down
            
    return print(lcs[::-1])
     
            
s1 = "ABCD"
s2 = "ACDF"


longest_common_subseq(s1, s2)

Q3. Select the different pieces of the rod in such a way that resultant profit is maximum.

Ans:

def rod_cutting(pieces, Profit):
    
    DP = [[0]*(pieces+1) for _ in range(len(Profit))]
    
    # Construct the table
    for i in range(1, len(Profit)):  # starting_range=1 coz 0 is the base 
        for j in range(1, pieces+1):
            if i <= j:  # if piece value is less than the profit
                DP[i][j] = max(DP[i-1][j], Profit[i]+DP[i][j-i]) ## DP[i-1][j] : exluding current piece
            else:
                DP[i][j] = DP[i-1][j]
    
    i = len(Profit)-1
    j = pieces
    
    while i > 0 and j > 0:
        if DP[i][j] == DP[i-1][j]:  ## if current and top cells are matching
            i -= 1
        else: # if current and top cells are not matching then take this 
            print("Take piece with length:", i, "meter")
            j -= i


# Example input
pieces = 5
Profit = [0, 2, 5, 7, 3, 9]

# Call the function
rod_cutting(pieces, Profit)

Output:

• Take piece with length: 2 meter
• Take piece with length: 2 meter
• Take piece with length: 1 meter