Rod Cutting

Same as Unbounded Knapsack

Problem Link: https://practice.geeksforgeeks.org/problems/rod-cutting0840/1

class Solution:
    def cutRod(self, price, n):
        #code here
        length=[]
        for i in range(1,n+1):
            length.append(i)
        dp=[[0 for i in range(n+1)] for j in range(n+1)]
        for i in range(n+1):
            for j in range(n+1):
                if(i==0 or j==0):
                    dp[i][j]=0
                else:
                    if(length[i-1]<=j):
                        cut=price[i-1]+dp[i][j-length[i-1]]
                        nocut=dp[i-1][j]
                        dp[i][j]=max(cut,nocut)
                    else:
                        dp[i][j]=dp[i-1][j]
        return dp[n][n]