Dynamic Programming Facts 1

Rod Cutting Problem

Problem:

Given a rod of length n inches and an array of prices that contains prices of all pieces of size
smaller than n. Determine the maximum value obtainable by cutting up the rod and selling the pieces.

Example: -

Input: Length of rod: 8 Prices: [1, 5, 8, 9, 10, 17, 17, 20] Output: 22 Explanation: - The maximum
obtainable value is by cutting the rod into two pieces of length 2 and 6. The price of the two
pieces is 5 + 17 = 22.

Complexity Analysis: -

Time Complexity: O(n^2) Space Complexity: O(n)

Solution:-

def rod_cutting(n, prices):
    dp = [0] * (n + 1)
    for i in range(1, n + 1):
        for j in range(i):
            dp[i] = max(dp[i], prices[j] + dp[i - j - 1])
    return dp[n]

---

Longest Common Subsequence

Problem:

Given a string, find the length of the longest palindromic subsequence.

Example:

Input: "bbbab" Output: 4 Explanation: The longest palindromic subsequence is "bbbb".

Complexity Analysis:

Time Complexity: O(n^2) Space Complexity: O(n^2)

Solution:

def longest_palindromic_subsequence(s):
    n = len(s)
    dp = [[0] * n for _ in range(n)]
    for i in range(n - 1, -1, -1):
        dp[i][i] = 1
        for j in range(i + 1, n):
            if s[i] == s[j]:
                dp[i][j] = 2 + dp[i + 1][j - 1]
            else:
                dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])
    return dp[0][n - 1]

---