Tiling and Splitting Problems: Backtracking meets DP

def tile_ways(n):
    # DP: dp[i] = ways to tile 2×i board
    # dp[i] = dp[i-1] + dp[i-2] (vertical or horizontal pair)
    if n <= 0: return 1
    dp = [0] * (n + 1)
    dp[0] = dp[1] = 1
    for i in range(2, n + 1):
        dp[i] = dp[i-1] + dp[i-2]
    return dp[n]

# Profile DP for general tilings
# State = column profile bitmask
def tiling_2xn(n):
    MOD = 10**9 + 7
    # ways to tile 2×n: Fibonacci!
    a, b = 1, 1
    for _ in range(n - 1):
        a, b = b, (a + b) % MOD
    return b

# 1547. Minimum Cost to Cut a Stick
# Interval DP: cost of cuts on stick of length n
def minCost(n, cuts):
    cuts = sorted([0] + cuts + [n])
    m = len(cuts)
    # dp[i][j] = min cost to cut segment cuts[i]..cuts[j]
    dp = [[0]*m for _ in range(m)]
    for length in range(2, m):
        for i in range(m - length):
            j = i + length
            dp[i][j] = float('inf')
            for k in range(i+1, j):
                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j] + cuts[j] - cuts[i])
    return dp[0][m-1]

# Burst Balloons: classic interval DP with in-between element
def maxCoins(nums):
    nums = [1] + nums + [1]
    n = len(nums)
    dp = [[0]*n for _ in range(n)]
    for length in range(2, n):
        for left in range(n - length):
            right = left + length
            for k in range(left+1, right):
                dp[left][right] = max(dp[left][right],
                    nums[left]*nums[k]*nums[right] + dp[left][k] + dp[k][right])
    return dp[0][n-1]

#include <bits/stdc++.h>
using namespace std;

// Burst Balloons
int maxCoins(vector<int>& nums) {
    nums.insert(nums.begin(), 1);
    nums.push_back(1);
    int n = nums.size();
    vector<vector<int>> dp(n, vector<int>(n, 0));
    for (int len = 2; len < n; len++) {
        for (int l = 0; l < n - len; l++) {
            int r = l + len;
            for (int k = l+1; k < r; k++) {
                dp[l][r] = max(dp[l][r],
                    nums[l]*nums[k]*nums[r] + dp[l][k] + dp[k][r]);
            }
        }
    }
    return dp[0][n-1];
}