Problem statement

https://binarysearch.com/problems/Rod-Cutting/

Solution

Let dp(i) is the answer to cut rod of length i. Then we can use dp to solve it.

Complexity

It is O(n^2) for time and O(n) for space.

Code

class Solution:
    def solve(self, P, n):
        @lru_cache(None)
        def dp(i):
            if i == 0: return 0
            return max(dp(i - k - 1) + P[k] for k in range(i))

        return dp(n)