区间 DP

问题描述

区间动态规划是指在区间上进行状态转移的问题。
常见的有石子合并、回文串判定等。
通常需要定义状态表示区间[i,j]上的最优解。

石子合并

算法思想

定义dp[i][j]表示将区间[i,j]内的石子合并的最小代价
枚举区间长度和起点，然后枚举分割点
状态转移方程：dp[i][j] = min(dp[i][k] + dp[k+1][j] + sum[i,j])
最终答案为dp[1][n]

代码实现

c++
java
python

int mergeStones(vector<int>& stones) {
    int n = stones.size();
    vector<int> sum(n + 1);
    vector<vector<int>> dp(n + 1, vector<int>(n + 1, INT_MAX));
    
    // 前缀和
    for (int i = 1; i <= n; i++) {
        sum[i] = sum[i-1] + stones[i-1];
    }
    
    // 初始化长度为1的区间
    for (int i = 1; i <= n; i++) {
        dp[i][i] = 0;
    }
    
    // 枚举区间长度
    for (int len = 2; len <= n; len++) {
        // 枚举左端点
        for (int i = 1; i + len - 1 <= n; i++) {
            int j = i + len - 1;
            // 枚举分割点
            for (int k = i; k < j; k++) {
                dp[i][j] = min(dp[i][j], 
                             dp[i][k] + dp[k+1][j] + sum[j] - sum[i-1]);
            }
        }
    }
    
    return dp[1][n];
}

public int mergeStones(int[] stones) {
    int n = stones.length;
    int[] sum = new int[n + 1];
    int[][] dp = new int[n + 1][n + 1];
    
    // 前缀和
    for (int i = 1; i <= n; i++) {
        sum[i] = sum[i-1] + stones[i-1];
    }
    
    // 初始化
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            dp[i][j] = Integer.MAX_VALUE;
        }
        dp[i][i] = 0;
    }
    
    // 枚举区间长度
    for (int len = 2; len <= n; len++) {
        for (int i = 1; i + len - 1 <= n; i++) {
            int j = i + len - 1;
            for (int k = i; k < j; k++) {
                dp[i][j] = Math.min(dp[i][j], 
                                  dp[i][k] + dp[k+1][j] + sum[j] - sum[i-1]);
            }
        }
    }
    
    return dp[1][n];
}

def mergeStones(stones: List[int]) -> int:
    n = len(stones)
    sum = [0] * (n + 1)
    dp = [[float('inf')] * (n + 1) for _ in range(n + 1)]
    
    # 前缀和
    for i in range(1, n + 1):
        sum[i] = sum[i-1] + stones[i-1]
    
    # 初始化长度为1的区间
    for i in range(1, n + 1):
        dp[i][i] = 0
    
    # 枚举区间长度
    for length in range(2, n + 1):
        for i in range(1, n - length + 2):
            j = i + length - 1
            for k in range(i, j):
                dp[i][j] = min(dp[i][j], 
                             dp[i][k] + dp[k+1][j] + sum[j] - sum[i-1])
    
    return dp[1][n]

回文串判定

算法思想

定义dp[i][j]表示区间[i,j]是否为回文串
如果s[i] == s[j]，则看[i+1,j-1]是否为回文串
状态转移方程：dp[i][j] = (s[i] == s[j]) && dp[i+1][j-1]
最终可以判断任意区间是否为回文串

代码实现

c++
java
python

vector<vector<bool>> palindrome(string s) {
    int n = s.length();
    vector<vector<bool>> dp(n, vector<bool>(n, false));
    
    // 长度为1的区间
    for (int i = 0; i < n; i++) {
        dp[i][i] = true;
    }
    
    // 枚举区间长度
    for (int len = 2; len <= n; len++) {
        for (int i = 0; i + len - 1 < n; i++) {
            int j = i + len - 1;
            if (len == 2) {
                dp[i][j] = (s[i] == s[j]);
            } else {
                dp[i][j] = (s[i] == s[j]) && dp[i+1][j-1];
            }
        }
    }
    
    return dp;
}

public boolean[][] palindrome(String s) {
    int n = s.length();
    boolean[][] dp = new boolean[n][n];
    
    // 长度为1的区间
    for (int i = 0; i < n; i++) {
        dp[i][i] = true;
    }
    
    // 枚举区间长度
    for (int len = 2; len <= n; len++) {
        for (int i = 0; i + len - 1 < n; i++) {
            int j = i + len - 1;
            if (len == 2) {
                dp[i][j] = (s.charAt(i) == s.charAt(j));
            } else {
                dp[i][j] = (s.charAt(i) == s.charAt(j)) && dp[i+1][j-1];
            }
        }
    }
    
    return dp;
}

def palindrome(s: str) -> List[List[bool]]:
    n = len(s)
    dp = [[False] * n for _ in range(n)]
    
    # 长度为1的区间
    for i in range(n):
        dp[i][i] = True
    
    # 枚举区间长度
    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            if length == 2:
                dp[i][j] = (s[i] == s[j])
            else:
                dp[i][j] = (s[i] == s[j] and dp[i+1][j-1])
    
    return dp

时间复杂度分析

算法时间复杂度空间复杂度

石子合并	$\mathcal{O}(n^3)$	$\mathcal{O}(n^2)$
回文串判定	$\mathcal{O}(n^2)$	$\mathcal{O}(n^2)$

应用场景

石子合并问题
回文串判定
矩阵链乘法
括号匹配
最优三角剖分

注意事项

区间遍历顺序
边界条件处理
状态转移正确性
区间大小限制
空间优化可能

经典例题

04.07_区间dp

区间 DP

问题描述

石子合并

算法思想

代码实现

回文串判定

算法思想

代码实现

时间复杂度分析

应用场景

注意事项

经典例题

全站热榜

创作者周榜