Given a rod of length N inches and an array of prices, price[]. price[i] denotes the value of a piece of length i. Determine the maximum value obtainable by cutting up the rod and selling the pieces.
Note: Consider 1-based indexing.
Example 1:
Input:
N = 8
Price[] = {1, 5, 8, 9, 10, 17, 17, 20}
Output:
22
Explanation:
The maximum obtainable value is 22 by 
cutting in two pieces of lengths 2 and 
6, i.e., 5+17=22.
Example 2:
Input:
N=8
Price[] = {3, 5, 8, 9, 10, 17, 17, 20}
Output: 
24
Explanation: 
The maximum obtainable value is 
24 by cutting the rod into 8 pieces 
of length 3, i.e, 8*3=24. 
Your Task:  
You don't need to read input or print anything. Your task is to complete the function cutRod() which takes the array A[] and its size N as inputs and returns the maximum price obtainable.
Expected Time Complexity: O(N^{2})
Expected Auxiliary Space: O(N)
Constraints:
1 ≤ N ≤ 1000
1 ≤ Ai ≤ 10^{5}

Difficulty: MEDIUM
Tags: Dynamic programming

Data structures
Skill types: Dynamic programming

Data structures
Expected Time Complexity: O(N^{2})
Expected Auxiliary Space: O(N)

Starter code:
#User function Template for python3



class Solution:

    def cutRod(self, price, n):

        #code here

Solutions:
import sys

class Solution:

	def cutRod(self, price, n):
		N = n
		cur = [0] * (N + 1)
		for i in range(N + 1):
			cur[i] = i * price[0]
		for ind in range(1, N):
			for length in range(N + 1):
				notTaken = 0 + cur[length]
				taken = float('-inf')
				rodLength = ind + 1
				if rodLength <= length:
					taken = price[ind] + cur[length - rodLength]
				cur[length] = max(notTaken, taken)
		return cur[N]


class Solution:

	def cutRod(self, price, n):
		cur = [0] * (n + 1)
		for target in range(n + 1):
			cur[target] = price[0] * target
		for i in range(1, n):
			for target in range(n + 1):
				not_pick = cur[target]
				pick = 0
				if i + 1 <= target:
					pick = price[i] + cur[target - (i + 1)]
				cur[target] = max(not_pick, pick)
		return cur[n]


class Solution:

	def dfs(self, i, target, price, dp):
		if i == 0:
			return price[0] * target
		if dp[i][target] != -1:
			return dp[i][target]
		not_pick = self.dfs(i - 1, target, price, dp)
		pick = 0
		if i + 1 <= target:
			pick = price[i] + self.dfs(i, target - (i + 1), price, dp)
		dp[i][target] = max(not_pick, pick)
		return dp[i][target]

	def cutRod(self, price, n):
		dp = [[-1 for j in range(n + 1)] for i in range(n)]
		return self.dfs(n - 1, n, price, dp)


class Solution:

	def cutRod(self, price, n):
		N = [i + 1 for i in range(n + 1)]
		dp = [[0 for i in range(n + 1)] for j in range(n + 1)]
		for i in range(1, n + 1):
			for j in range(1, n + 1):
				if N[i - 1] <= j:
					dp[i][j] = max(price[i - 1] + dp[i][j - N[i - 1]], dp[i - 1][j])
				else:
					dp[i][j] = dp[i - 1][j]
		return dp[n][n]


class Solution:

	def cutRod(self, price, n):
		dp = [[-1 for _ in range(n + 1)] for _ in range(n + 1)]
		for j in range(n + 1):
			dp[1][j] = j * price[0]
		for i in range(n + 1):
			dp[i][0] = 0
		for i in range(2, n + 1):
			for j in range(1, n + 1):
				np = -1000000000.0
				np = 0 + dp[i - 1][j]
				p = -1000000000.0
				if j >= i:
					p = price[i - 1] + dp[i][j - i]
				dp[i][j] = max(p, np)
		return dp[n][n]


class Solution:

	def cutRod(self, price, n):
		dp = [[-1 for _ in range(n + 1)] for _ in range(n + 1)]

		def f(index, length, dp):
			if length == 0:
				return 0
			if index == 1:
				return length * price[index - 1]
			if dp[index][length] != -1:
				return dp[index][length]
			np = 0 + f(index - 1, length, dp)
			p = -1000000000.0
			if length >= index:
				p = price[index - 1] + f(index, length - index, dp)
			dp[index][length] = max(p, np)
			return dp[index][length]
		return f(n, n, dp)


import sys

class Solution:

	def cutRod(self, price, n):
		dp = [0] * (n + 1)
		for i in range(n + 1):
			dp[i] = i * price[0]
		for i in range(1, n):
			for j in range(n + 1):
				notTaken = dp[j]
				taken = float('-inf')
				if j >= i + 1:
					taken = price[i] + dp[j - i - 1]
				dp[j] = max(taken, notTaken)
		return dp[n]


class Solution:

	def cutRod(self, arr, n):
		n = len(arr)
		dp = [[-1] * (n + 1) for i in range(n)]
		for c in range(n + 1):
			dp[0][c] = c * arr[0]
		for n in range(1, n):
			for c in range(len(arr) + 1):
				notTake = 0 + dp[n - 1][c]
				Take = -1000000000.0
				if n + 1 <= c:
					Take = dp[n][c - (n + 1)] + arr[n]
				dp[n][c] = max(notTake, Take)
		return dp[len(arr) - 1][len(arr)]


class Solution:

	def cutRod(self, price, n):
		dp = [0 for _ in range(n + 1)]
		dp[1] = price[0]
		if n == 1:
			return dp[1]
		for i in range(2, n + 1):
			mid = i // 2
			this_max = price[i - 1]
			for j in range(1, mid + 1):
				this_max = max(this_max, dp[i - j] + dp[j])
			dp[i] = this_max
		return dp[n]


class Solution:

	def cutRod(self, price, n):
		leng = []
		for i in range(1, n + 1):
			leng.append(i)
		dp = [[0 for i in range(n + 1)] for i in range(len(price) + 1)]
		for i in range(0, len(price) + 1):
			for j in range(0, n + 1):
				if leng[i - 1] <= j:
					dp[i][j] = max(price[i - 1] + dp[i][j - leng[i - 1]], dp[i - 1][j])
				else:
					dp[i][j] = dp[i - 1][j]
		return dp[len(price)][n]


class Solution:

	def cutRod(self, price, n):
		dp = [[-1 for i in range(n + 1)] for j in range(n + 1)]

		def recur(idx, target):
			if idx == 0:
				return target * price[0]
			if dp[idx][target] != -1:
				return dp[idx][target]
			if idx <= target:
				dp[idx][target] = max(price[idx - 1] + recur(idx, target - idx), recur(idx - 1, target))
			else:
				dp[idx][target] = recur(idx - 1, target)
			return dp[idx][target]
		return recur(n, n)


class Solution:

	def cutRod(self, price, n):
		rod = []
		for i in range(len(price)):
			rod.append(i + 1)
		target = n
		N = len(rod)
		dp = [[0 for j in range(target + 1)] for i in range(N + 1)]
		for i in range(N + 1):
			for j in range(target + 1):
				if i == 0 or j == 0:
					dp[i][j] = 0
				elif rod[i - 1] > j:
					dp[i][j] = dp[i - 1][j]
				else:
					dp[i][j] = max(dp[i - 1][j], price[i - 1] + dp[i][j - rod[i - 1]])
		return dp[N][target]


class Solution:

	def cutRod(self, price, n):
		m = len(price)
		dp = [[0 for i in range(n + 1)] for j in range(m + 1)]
		length = [i + 1 for i in range(m)]
		for i in range(1, m + 1):
			for j in range(1, n + 1):
				if i <= j:
					dp[i][j] = max(price[i - 1] + dp[i][j - i], dp[i - 1][j])
				else:
					dp[i][j] = dp[i - 1][j]
		return dp[m][n]


class Solution:

	def cutRod(self, price, n):
		dp = [0] * (n + 1)
		for length in range(1, n + 1):
			for cut_length in range(1, length + 1):
				dp[length] = max(dp[length], price[cut_length - 1] + dp[length - cut_length])
		return dp[n]


class Solution:

	def cutRod(self, price, n):
		N = n
		length = []
		for i in range(1, N + 1):
			length.append(i)
		n = len(length)
		t = [[-1 for i in range(N + 1)] for j in range(n + 1)]
		for i in range(N + 1):
			t[0][i] = 0
		for i in range(n + 1):
			t[i][0] = 0
		for i in range(1, n + 1):
			for j in range(1, N + 1):
				if length[i - 1] <= j:
					t[i][j] = max(price[i - 1] + t[i][j - length[i - 1]], t[i - 1][j])
				else:
					t[i][j] = t[i - 1][j]
		return t[n][N]


class Solution:

	def cutRod(self, price, n):
		l = [i for i in range(1, n + 1)]
		m = len(l)
		t = [[0 for j in range(n + 1)] for j in range(n + 1)]
		for i in range(1, n + 1):
			for j in range(1, n + 1):
				if l[i - 1] <= j:
					t[i][j] = max(price[i - 1] + t[i][j - l[i - 1]], t[i - 1][j])
				else:
					t[i][j] = t[i - 1][j]
		return t[n][n]


class Solution:

	def cutRod(self, price, l):
		n = len(price)
		dp = [[-1 for j in range(l + 1)] for i in range(n)]
		return self.solve(n - 1, l, dp, price)

	def solve(self, n, l, dp, price):
		import sys
		if n == 0:
			if n + 1 <= l:
				dp[n][l] = price[n] * l
				return dp[n][l]
			else:
				dp[n][l] = 0
				return 0
		if dp[n][l] != -1:
			return dp[n][l]
		pick = -sys.maxsize
		npick = 0 + self.solve(n - 1, l, dp, price)
		if n + 1 <= l:
			pick = price[n] + self.solve(n, l - (n + 1), dp, price)
		dp[n][l] = max(pick, npick)
		return dp[n][l]


class Solution:

	def cutRod(self, cuts, n):
		l = []
		for i in range(1, n + 1):
			l.append(i)
		dp = [0] * (n + 1)
		for i in range(1, len(cuts) + 1):
			for j in range(1, n + 1):
				if l[i - 1] <= j:
					dp[j] = max(dp[j], dp[j - l[i - 1]] + cuts[i - 1])
				else:
					dp[j] = dp[j]
		return dp[n]


class Solution:

	def cutRod(self, price, N):
		dp = [0] * (N + 1)
		for i in range(1, N + 1):
			max_val = float('-inf')
			for j in range(1, i + 1):
				max_val = max(max_val, price[j - 1] + dp[i - j])
			dp[i] = max_val
		return dp[N]


class Solution:

	def cutRod(self, price, n):
		table = [[0 for x in range(n + 1)] for y in range(n + 1)]
		for i in range(1, n + 1):
			for j in range(1, n + 1):
				if i <= j:
					table[i][j] = max(table[i - 1][j], price[i - 1] + table[i][j - i])
				else:
					table[i][j] = table[i - 1][j]
		return table[n][n]


class Solution:

	def cutRod(self, price, n):
		dp = [0 for x in range(n + 1)]
		for rodLen in range(1, n + 1):
			max = 0
			for i in range(rodLen):
				if i <= rodLen:
					rRodLen = rodLen - i - 1
					rRodLenPrice = dp[rRodLen]
					tRodLenPrice = rRodLenPrice + price[i]
					if tRodLenPrice > max:
						max = tRodLenPrice
			dp[rodLen] = max
		return dp[n]


class Solution:

	def cutRod(self, arr, n):
		N = []
		for i in range(len(arr)):
			N.append(i + 1)
		W = len(arr)
		dp = [[0 for i in range(n + 1)] for j in range(W + 1)]
		for i in range(1, W + 1):
			for j in range(1, n + 1):
				if N[i - 1] <= j:
					dp[i][j] = max(arr[i - 1] + dp[i][j - N[i - 1]], dp[i - 1][j])
				else:
					dp[i][j] = dp[i - 1][j]
		return dp[W][n]


class Solution:

	def cutRod(self, price, n):
		P = len(price)
		dp = [[0] * (n + 1) for _ in range(P + 1)]
		for r in range(1, n + 1):
			for c in range(1, P + 1):
				if r <= c:
					dp[r][c] = max(price[r - 1] + dp[r][c - r], dp[r - 1][c])
				else:
					dp[r][c] = dp[r - 1][c]
		return dp[-1][-1]


class Solution:

	def cutRod(self, price, n):
		dp = [[-1 for i in range(n + 1)] for i in range(n + 1)]
		return self.cut(price, n, n, dp)

	def cut(self, price, target, ind, dp):
		if dp[ind][target] != -1:
			return dp[ind][target]
		if ind == 1:
			dp[ind][target] = price[ind - 1] * target
			return price[ind - 1] * target
		notpick = self.cut(price, target, ind - 1, dp)
		pick = -10 ** 8
		if target >= ind:
			pick = price[ind - 1] + self.cut(price, target - ind, ind, dp)
		dp[ind][target] = max(pick, notpick)
		return dp[ind][target]


class Solution:

	def cutRod(self, price, n):
		P = []
		for i in range(1, n + 1):
			m = 0
			if i <= len(price) + 1:
				m = price[i - 1]
			if P != []:
				for (i, p) in enumerate(P):
					m = max(m, p + P[-(i + 1)])
			P.append(m)
		return P[-1]


class Solution:

	def cutRod(self, p, n):
		dp = [0 for i in range(n + 1)]
		temp = [0 for i in range(n + 1)]
		for i in range(n + 1):
			dp[i] = i * p[0]
		for i in range(2, n + 1):
			for j in range(1, n + 1):
				x = dp[j]
				y = -float('inf')
				if i <= j:
					y = p[i - 1] + temp[j - i]
				temp[j] = max(x, y)
			dp = temp
		return dp[n]


class Solution:

	def cutRod(self, price, n):
		dp = [[-1 for i in range(n + 1)] for j in range(n + 1)]

		def sum(i, n, p, dp):
			if i == 1:
				return n * p[0]
			if dp[i][n] != -1:
				return dp[i][n]
			x = sum(i - 1, n, p, dp)
			y = -float('inf')
			if i <= n:
				y = p[i - 1] + sum(i, n - i, p, dp)
			dp[i][n] = max(x, y)
			return dp[i][n]
		return sum(n, n, price, dp)


from collections import deque

class Solution:

	def cutRod(self, price, n):
		sub_max = [price[0]]
		for sub_n in range(2, n + 1):
			options_holder = [price[sub_n - 1]]
			for i in range(1, sub_n):
				options_holder.append(sub_max[-i] + sub_max[i - 1])
			sub_max.append(max(options_holder))
		return sub_max[-1]


class Solution:

	def cutRod(self, price, N):
		dp = [[0 for i in range(N + 1)] for j in range(N + 1)]
		for i in range(1, N + 1):
			dp[1][i] = price[0] * i
		for i in range(2, N + 1):
			for j in range(1, N + 1):
				include = 0
				if j >= i:
					include = dp[i][j - i] + price[i - 1]
				dp[i][j] = max(include, dp[i - 1][j])
		return dp[N][N]


class Solution:

	def cutRod(self, price, n):
		ans = [-1] * (n + 1)
		ans[0] = 0
		for i in range(1, n + 1):
			for j in range(1, i + 1):
				ans[i] = max(ans[i], price[j - 1] + ans[i - j])
		return ans[n]


class Solution:

	def cutRod(self, price, n):
		le_arr = [x for x in range(1, n + 1)]
		dp = [[0 for _ in range(n + 1)] for _ in range(n + 1)]
		for i in range(1, n + 1):
			for j in range(1, n + 1):
				if le_arr[i - 1] <= j:
					dp[i][j] = max(price[i - 1] + dp[i][j - le_arr[i - 1]], dp[i - 1][j])
				else:
					dp[i][j] = dp[i - 1][j]
		return dp[n][n]


class Solution:

	def solve(self, n, cost, dp):
		if n == 0:
			return 0
		if n < 0:
			return -10000000000.0
		maxi = 0
		for i in range(n):
			ans = cost[i] + self.solve(n - (i + 1), cost, dp)
			maxi = max(maxi, ans)
		dp[n] = maxi
		return dp[n]

	def cutRod(self, price, n):
		dp = [0 for _ in range(n + 1)]
		for i in range(1, n + 1):
			maxi = 0
			for j in range(i):
				ans = price[j] + dp[i - j - 1]
				maxi = max(ans, maxi)
			dp[i] = maxi
		return dp[n]


class Solution:

	def cutRod(self, price, n):
		T = [[0 for i in range(n + 1)] for i in range(n + 1)]
		for i in range(n + 1):
			for j in range(n + 1):
				if i == 0 or j == 0:
					T[i][j] = 0
				elif i <= j:
					T[i][j] = max(price[i - 1] + T[i][j - i], T[i - 1][j])
				else:
					T[i][j] = T[i - 1][j]
		return T[n][n]


class Solution:

	def helper(self, i, length, price, n, dp):
		if i > n:
			return 0
		if dp[i - 1][length] != -1:
			return dp[i - 1][length]
		cutRod = -1000000000.0
		if i <= length:
			cutRod = price[i - 1] + self.helper(i, length - i, price, n, dp)
		notCutRod = self.helper(i + 1, length, price, n, dp)
		dp[i - 1][length] = max(cutRod, notCutRod)
		return dp[i - 1][length]

	def cutRod(self, price, n):
		dp = [[-1] * (n + 1) for i in range(n + 1)]
		return self.helper(1, n, price, n, dp)


class Solution:

	def cutRod(self, price, n):
		return self.space_tab_find_max_price(price, n, n)

	def find_max_price(self, curr_index, last_index, rod_length, price, memo):
		if rod_length == 0:
			return 0
		if curr_index == last_index:
			return price[curr_index] if curr_index + 1 <= rod_length else 0
		if memo[curr_index][rod_length] != None:
			return memo[curr_index][rod_length]
		consider = 0
		curr_cut_piece = curr_index + 1
		if curr_cut_piece <= rod_length:
			balance_rod_length = rod_length - curr_cut_piece
			consider = price[curr_index] + self.find_max_price(curr_index, last_index, balance_rod_length, price, memo)
		not_consider = self.find_max_price(curr_index + 1, last_index, rod_length, price, memo)
		memo[curr_index][rod_length] = max(consider, not_consider)
		return memo[curr_index][rod_length]

	def tab_find_max_price(self, price, rod_length, max_pieces, memo):
		for curr_index in range(max_pieces - 1, -1, -1):
			for available_rod_length in range(0, rod_length + 1, 1):
				if available_rod_length == 0:
					memo[curr_index][available_rod_length] = 0
					continue
				if curr_index == max_pieces - 1:
					memo[curr_index][available_rod_length] = price[curr_index] if curr_index + 1 <= available_rod_length else 0
					continue
				consider = 0
				curr_cut_piece = curr_index + 1
				if curr_cut_piece <= available_rod_length:
					balance_rod_length = available_rod_length - curr_cut_piece
					consider = price[curr_index] + memo[curr_index][balance_rod_length]
				not_consider = memo[curr_index + 1][available_rod_length]
				memo[curr_index][available_rod_length] = max(consider, not_consider)
		return memo[0][rod_length]

	def space_tab_find_max_price(self, price, rod_length, max_pieces):
		prev = None
		for curr_index in range(max_pieces - 1, -1, -1):
			temp = [0 for length in range(rod_length + 1)]
			for available_rod_length in range(0, rod_length + 1, 1):
				if available_rod_length == 0:
					temp[available_rod_length] = 0
					continue
				if curr_index == max_pieces - 1:
					temp[available_rod_length] = price[curr_index] if curr_index + 1 <= available_rod_length else 0
					continue
				consider = 0
				curr_cut_piece = curr_index + 1
				if curr_cut_piece <= available_rod_length:
					balance_rod_length = available_rod_length - curr_cut_piece
					consider = price[curr_index] + temp[balance_rod_length]
				not_consider = prev[available_rod_length]
				temp[available_rod_length] = max(consider, not_consider)
			prev = temp
		return prev[rod_length]


class Solution:

	def cutRod(self, price, n):
		memo = [[0 for curr_piece in range(n + 1)] for index in range(n)]
		return self.tab_find_max_price(price, n, n, memo)

	def find_max_price(self, curr_index, last_index, rod_length, price, memo):
		if rod_length == 0:
			return 0
		if curr_index == last_index:
			return price[curr_index] if curr_index + 1 <= rod_length else 0
		if memo[curr_index][rod_length] != None:
			return memo[curr_index][rod_length]
		consider = 0
		curr_cut_piece = curr_index + 1
		if curr_cut_piece <= rod_length:
			balance_rod_length = rod_length - curr_cut_piece
			consider = price[curr_index] + self.find_max_price(curr_index, last_index, balance_rod_length, price, memo)
		not_consider = self.find_max_price(curr_index + 1, last_index, rod_length, price, memo)
		memo[curr_index][rod_length] = max(consider, not_consider)
		return memo[curr_index][rod_length]

	def tab_find_max_price(self, price, rod_length, max_pieces, memo):
		for curr_index in range(max_pieces - 1, -1, -1):
			for available_rod_length in range(0, rod_length + 1, 1):
				if available_rod_length == 0:
					memo[curr_index][available_rod_length] = 0
					continue
				if curr_index == max_pieces - 1:
					memo[curr_index][available_rod_length] = price[curr_index] if curr_index + 1 <= available_rod_length else 0
					continue
				consider = 0
				curr_cut_piece = curr_index + 1
				if curr_cut_piece <= available_rod_length:
					balance_rod_length = available_rod_length - curr_cut_piece
					consider = price[curr_index] + memo[curr_index][balance_rod_length]
				not_consider = memo[curr_index + 1][available_rod_length]
				memo[curr_index][available_rod_length] = max(consider, not_consider)
		return memo[0][rod_length]


def rodCutting(p, n):
	size = len(p)
	dp = [0] * size
	for i in range(1, size):
		for j in range(i, 0, -1):
			value = p[j] + dp[i - j]
			if value > dp[i]:
				dp[i] = value
	return dp[n]

class Solution:

	def cutRod(self, price, n):
		price.insert(0, 0)
		return rodCutting(price, n)


class Solution:

	def cutRod(self, price, n):
		d = len(price)
		prev = [0 for i in range(n + 1)]
		for i in range(n + 1):
			prev[i] = i // (0 + 1) * price[0]
		for ind in range(1, d):
			for length in range(n + 1):
				notCut = 0 + prev[length]
				Cut = 0
				if ind + 1 <= length:
					Cut = price[ind] + prev[length - ind - 1]
				prev[length] = max(Cut, notCut)
		return prev[n]


class Solution:

	def cutRod(self, price, n):
		dp = [0] * (n + 1)
		dp[0] = 0
		for (i, p) in enumerate(price):
			dp[i + 1] = p
		for i in range(1, n + 1):
			for j in range(0, i):
				dp[i] = max(dp[i], dp[j] + dp[i - j])
		return dp[n]


class Solution:

	def cutRod(self, price, n):
		dp = [0] * (n + 1)
		for i in range(1, n + 1):
			for j in range(1, n + 1):
				not_taken = dp[j]
				taken = float('-inf')
				if j >= i:
					taken = price[i - 1] + dp[j - i]
				dp[j] = max(taken, not_taken)
		return max(dp)


class Solution:

	def rod(self, c, n, wt, vl, dp):
		if n == 0 or c == 0:
			return 0
		if dp[n][c] != -1:
			return dp[n][c]
		if wt[n - 1] > c:
			dp[n][c] = self.rod(c, n - 1, wt, vl, dp)
			return dp[n][c]
		else:
			dp[n][c] = max(vl[n - 1] + self.rod(c - wt[n - 1], n, wt, vl, dp), self.rod(c, n - 1, wt, vl, dp))
			return dp[n][c]

	def cutRod(self, price, n):
		length = [i for i in range(1, n + 1)]
		dp = [[-1 for i in range(n + 1)] for _ in range(len(price) + 1)]
		return self.rod(n, len(price), length, price, dp)


class Solution:

	def f(self, ind, target, arr, dp):
		if ind == 0:
			return target * arr[0]
			if dp[ind][target] != -1:
				return dp[ind][target]
		ntake = 0 + self.f(ind - 1, target, arr, dp)
		take = -1000000000.0
		if ind + 1 <= target:
			take = arr[ind] + self.f(ind, target - (ind + 1), arr, dp)
		dp[ind][target] = max(take, ntake)
		return dp[ind][target]

	def cutRod(self, price, n):
		arr = price
		dp = [[0 for i in range(n + 1)] for i in range(n)]
		for target in range(n + 1):
			dp[0][target] = target * arr[0]
		for ind in range(1, n):
			for target in range(n + 1):
				ntake = dp[ind - 1][target]
				take = -1000000000.0
				if ind + 1 <= target:
					take = arr[ind] + dp[ind][target - ind - 1]
				dp[ind][target] = max(take, ntake)
		return dp[n - 1][n]


class Solution:

	def cutRod(self, price, N):
		dp = [[0] * (N + 1) for _ in range(N + 1)]
		for i in range(N + 1):
			for j in range(N + 1):
				cl = i
				rl = j
				if cl == 0 or rl == 0:
					dp[i][j] = 0
				else:
					val = price[cl - 1]
					if cl <= rl:
						dp[i][j] = max(val + dp[cl][rl - cl], dp[cl - 1][rl])
					else:
						dp[i][j] = dp[cl - 1][rl]
		return dp[N][N]


class Solution:

	def cutRod(self, price, N):
		dp = {}

		def solve(cl, rl):
			if cl == 0 or rl == 0:
				return 0
			elif (cl, rl) in dp:
				return dp[cl, rl]
			else:
				val = price[cl - 1]
				if cl <= rl:
					c1 = val + solve(cl, rl - cl)
					c2 = solve(cl - 1, rl)
					c = max(c1, c2)
				else:
					c = solve(cl - 1, rl)
				dp[cl, rl] = c
				return c
		return solve(N, N)


class Solution:

	def cutRod(self, price, n):
		dp = {}

		def cut(i, temp_length):
			if i == n - 1:
				if i + 1 <= temp_length:
					return price[i]
				else:
					return 0
			if (i, temp_length) in dp:
				return dp[i, temp_length]
			inc = 0
			if i + 1 <= temp_length:
				inc = price[i] + cut(i, temp_length - (i + 1))
			enc = 0 + cut(i + 1, temp_length)
			dp[i, temp_length] = max(inc, enc)
			return dp[i, temp_length]
		return cut(0, n)


class Solution:

	def cutRod(self, price, n):
		rodLength = n
		n = len(price)
		dp = [[0 for i in range(rodLength + 1)] for j in range(n + 1)]
		for i in range(1, n + 1):
			for j in range(1, rodLength + 1):
				dp[i][j] = dp[i - 1][j]
				if i <= j:
					dp[i][j] = max(dp[i][j], price[i - 1] + dp[i][j - i])
		return dp[n][rodLength]


class Solution:

	def cutRod(self, price, n):
		ans = [0] * (n + 1)
		ans[1] = price[0]
		for i in range(2, n + 1):
			for cut in range(1, i + 1):
				ans[i] = max(ans[i], price[cut - 1] + ans[i - cut])
		return ans[n]


import sys

class Solution:

	def cutRod(self, price, n):
		N = n
		dp = [[-1 for j in range(N + 1)] for i in range(N)]
		for i in range(N + 1):
			dp[0][i] = i * price[0]
		for ind in range(1, N):
			for length in range(N + 1):
				notTaken = 0 + dp[ind - 1][length]
				taken = -sys.maxsize
				rodLength = ind + 1
				if rodLength <= length:
					taken = price[ind] + dp[ind][length - rodLength]
				dp[ind][length] = max(notTaken, taken)
		return dp[N - 1][N]


class Solution:

	def cutRod(self, price, n):
		dp = {}

		def rod(pos, wt):
			if pos == 0:
				return wt * price[0]
			if (pos, wt) in dp:
				return dp[pos, wt]
			include = 0
			rod_length = pos + 1
			if rod_length <= wt:
				include = price[pos] + rod(pos, wt - rod_length)
			exclude = 0 + rod(pos - 1, wt)
			dp[pos, wt] = max(include, exclude)
			return dp[pos, wt]
		return rod(n - 1, n)


class Solution:

	def cutRod(self, price, n):
		dp = [[-1 for _ in range(n + 1)] for _ in range(n + 1)]

		def f(idx, tar, arr, dp):
			if tar < 0:
				return 0
			if idx == 0:
				return tar // (idx + 1) * arr[0]
			if dp[idx][tar] != -1:
				return dp[idx][tar]
			take = 0
			if idx + 1 <= tar:
				take = arr[idx] + f(idx, tar - (idx + 1), arr, dp)
			nottake = 0 + f(idx - 1, tar, arr, dp)
			dp[idx][tar] = max(take, nottake)
			return dp[idx][tar]
		return f(n - 1, n, price, dp)


class Solution:

	def cutRod(self, price, n):
		wt = []
		for i in range(1, n + 1):
			wt.append(i)
		dp = [[-1 for i in range(n + 1)] for j in range(n)]

		def helper(idx, n):
			if n < 0:
				return -float('inf')
			if idx == 0:
				return n // wt[0] * price[0]
			if dp[idx][n] != -1:
				return dp[idx][n]
			not_take = helper(idx - 1, n)
			take = -float('inf')
			if wt[idx] <= n:
				take = price[idx] + helper(idx, n - wt[idx])
			dp[idx][n] = max(not_take, take)
			return dp[idx][n]
		return helper(n - 1, n)


class Solution:

	def cutRod(self, price, W):
		n = len(price)
		rod = [i for i in range(1, W + 1)]
		dp = [[0 for i in range(W + 1)] for j in range(n + 1)]
		for i in range(1, n + 1):
			for j in range(1, W + 1):
				if rod[i - 1] <= j:
					dp[i][j] = max(price[i - 1] + dp[i][j - rod[i - 1]], dp[i - 1][j])
				else:
					dp[i][j] = dp[i - 1][j]
		return dp[n][W]


class Solution:

	def cutRod(self, price, n):
		memo = {}

		def traverse(length):
			if length == 0:
				return 0
			if length in memo:
				return memo[length]
			profit = 0
			for i in range(1, length + 1):
				profit = max(profit, price[i - 1] + traverse(length - i))
			memo[length] = profit
			return memo[length]
		return traverse(n)


import numpy

class Solution:

	def cutRod(self, price, n):
		val = [0] * (n + 1)
		for i in range(1, n + 1):
			max_val = -1
			for j in range(i):
				max_val = max(max_val, price[j] + val[i - j - 1])
			val[i] = max_val
		return val[n]


class Solution:

	def cutRod(self, price, n):
		arr = price
		l = [i for i in range(1, n + 1)]
		m = len(l)
		t = [[None] * (m + 1) for i in range(n + 1)]
		for i in range(n + 1):
			for j in range(m + 1):
				if i == 0 or j == 0:
					t[i][j] = 0
		for i in range(1, n + 1):
			for j in range(1, n + 1):
				if l[i - 1] <= j:
					t[i][j] = max(arr[i - 1] + t[i][j - l[i - 1]], t[i - 1][j])
				elif l[i - 1] > j:
					t[i][j] = t[i - 1][j]
		return t[n][m]


class Solution:

	def cutRod(self, price, n):
		length = [x for x in range(1, n + 1)]
		res = [[0 for _ in range(n + 1)] for x in range(n + 1)]
		for i in range(1, n + 1):
			for j in range(1, n + 1):
				if length[i - 1] <= j:
					res[i][j] = max(price[i - 1] + res[i][j - length[i - 1]], res[i - 1][j])
				else:
					res[i][j] = res[i - 1][j]
		return res[n][n]


class Solution:

	def cutRod(self, price, n):

		def solve(i, price, n, dp):
			if dp[i][n] != -1:
				return dp[i][n]
			nt = solve(i - 1, price, n, dp)
			t = -1
			if i + 1 <= n:
				t = price[i] + solve(i, price, n - (i + 1), dp)
			dp[i][n] = max(t, nt)
			return dp[i][n]
		dp = [[-1 for i in range(n + 1)] for j in range(n + 1)]
		for i in range(n + 1):
			dp[0][i] = price[0] * i
		return int(solve(n - 1, price, n, dp))


class Solution:

	def cutRod(self, price, n):
		arr = [i + 1 for i in range(n)]
		t = [[0 for j in range(n + 1)] for i in range(n + 1)]
		for i in range(n + 1):
			for j in range(n + 1):
				if i == 0 or j == 0:
					t[i][j] = 0
		for i in range(1, n + 1):
			for j in range(1, n + 1):
				if arr[i - 1] <= j:
					t[i][j] = max(price[i - 1] + t[i][j - arr[i - 1]], t[i - 1][j])
				else:
					t[i][j] = t[i - 1][j]
		return t[n][n]


from functools import lru_cache

class Solution:

	def cutRod(self, arr, n):
		l = [i for i in range(1, n + 1)]
		m = len(l)
		t = [[None] * (m + 1) for i in range(n + 1)]
		for i in range(n + 1):
			for j in range(m + 1):
				if i == 0 or j == 0:
					t[i][j] = 0
		for i in range(1, n + 1):
			for j in range(1, n + 1):
				if l[i - 1] <= j:
					t[i][j] = max(arr[i - 1] + t[i][j - l[i - 1]], t[i - 1][j])
				elif l[i - 1] > j:
					t[i][j] = t[i - 1][j]
		return t[n][m]


from functools import lru_cache

class Solution:

	def cutRod(self, price, n):

		@lru_cache(None)
		def fun(left=n):
			if not left:
				return 0
			mx = float('-inf')
			for i in range(left):
				res = price[i] + fun(left - i - 1)
				mx = max(mx, res)
			return mx
		return fun()


class Solution:

	def helper(self, i, price, n, dp):
		if i >= n:
			return 0
		if n <= 0:
			return 0
		if dp[i][n] != -1:
			return dp[i][n]
		cut = price[i] + self.helper(i, price, n - i - 1, dp)
		notCut = self.helper(i + 1, price, n, dp)
		dp[i][n] = max(cut, notCut)
		return dp[i][n]

	def cutRod(self, price, n):
		dp = [[-1] * (n + 1) for i in range(n + 1)]
		return self.helper(0, price, n, dp)


class Solution:

	def maxValue(self, index, n, price, dp):
		if index == 0:
			return price[index] * n
		if dp[index][n] != -1:
			return dp[index][n]
		notTake = self.maxValue(index - 1, n, price, dp)
		take = -100000000.0
		if index + 1 <= n:
			take = price[index] + self.maxValue(index, n - (index + 1), price, dp)
		dp[index][n] = max(take, notTake)
		return max(take, notTake)

	def cutRod(self, price, n):
		dp = [[-1 for i in range(n + 2)] for row in range(n)]
		return self.maxValue(n - 1, n, price, dp)