百练百会 bestWit

Appearance

L7_02 复杂动态规划 ​

一、二维动态规划 ​

1.1 二维动态规划概述 ​

二维动态规划使用二维数组来存储状态，适用于涉及两个维度的问题。

1.2 二维背包问题 ​

cpp
int knapsack2D(vector<int>& weights, vector<int>& volumes, 
               vector<int>& values, int maxWeight, int maxVolume) {
    int n = weights.size();
    vector<vector<int>> dp(maxWeight + 1, vector<int>(maxVolume + 1, 0));
    
    for (int i = 0; i < n; i++) {
        for (int w = maxWeight; w >= weights[i]; w--) {
            for (int v = maxVolume; v >= volumes[i]; v--) {
                dp[w][v] = max(dp[w][v], dp[w - weights[i]][v - volumes[i]] + values[i]);
            }
        }
    }
    return dp[maxWeight][maxVolume];
}

1.3 最长公共子序列(LCS) ​

cpp
int longestCommonSubsequence(string text1, string text2) {
    int m = text1.size(), n = text2.size();
    vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
    
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (text1[i - 1] == text2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }
    return dp[m][n];
}

二、动态规划最值优化 ​

2.1 最大子矩阵和 ​

cpp
int maxSubmatrixSum(vector<vector<int>>& matrix) {
    int rows = matrix.size();
    int cols = matrix[0].size();
    int max_sum = INT_MIN;
    
    for (int left = 0; left < cols; left++) {
        vector<int> row_sums(rows, 0);
        for (int right = left; right < cols; right++) {
            for (int i = 0; i < rows; i++) {
                row_sums[i] += matrix[i][right];
            }
            // 使用一维最大子数组和算法
            int current_sum = 0, current_max = INT_MIN;
            for (int sum : row_sums) {
                current_sum = max(sum, current_sum + sum);
                current_max = max(current_max, current_sum);
            }
            max_sum = max(max_sum, current_max);
        }
    }
    return max_sum;
}

2.2 最大正方形 ​

cpp
int maximalSquare(vector<vector<char>>& matrix) {
    int rows = matrix.size();
    int cols = matrix[0].size();
    vector<vector<int>> dp(rows, vector<int>(cols, 0));
    int max_side = 0;
    
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            if (matrix[i][j] == '1') {
                if (i == 0 || j == 0) {
                    dp[i][j] = 1;
                } else {
                    dp[i][j] = min({dp[i-1][j], dp[i][j-1], dp[i-1][j-1]}) + 1;
                }
                max_side = max(max_side, dp[i][j]);
            }
        }
    }
    return max_side * max_side;
}

三、区间动态规划 ​

3.1 区间DP概述 ​

区间动态规划是一种特殊的动态规划，状态定义通常为 dp[i][j] 表示区间 [i, j] 的最优解。

3.2 石子合并问题 ​

cpp
int stoneGame(vector<int>& stones) {
    int n = stones.size();
    vector<vector<int>> dp(n, vector<int>(n, 0));
    vector<int> prefix(n + 1, 0);
    
    for (int i = 0; i < n; i++) {
        prefix[i + 1] = prefix[i] + stones[i];
    }
    
    for (int len = 2; len <= n; len++) {
        for (int i = 0; i + len <= n; i++) {
            int j = i + len - 1;
            dp[i][j] = INT_MAX;
            int sum = prefix[j + 1] - prefix[i];
            for (int k = i; k < j; k++) {
                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + sum);
            }
        }
    }
    return dp[0][n - 1];
}

3.3 最长回文子序列 ​

cpp
int longestPalindromeSubseq(string s) {
    int n = s.size();
    vector<vector<int>> dp(n, vector<int>(n, 0));
    
    for (int i = n - 1; i >= 0; i--) {
        dp[i][i] = 1;
        for (int j = i + 1; j < n; j++) {
            if (s[i] == s[j]) {
                dp[i][j] = dp[i + 1][j - 1] + 2;
            } else {
                dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);
            }
        }
    }
    return dp[0][n - 1];
}

四、最长上升子序列(LIS) ​

4.1 O(n²) 解法 ​

cpp
int lengthOfLIS(vector<int>& nums) {
    int n = nums.size();
    vector<int> dp(n, 1);
    
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (nums[i] > nums[j]) {
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
    }
    return *max_element(dp.begin(), dp.end());
}

4.2 O(n log n) 解法 ​

cpp
int lengthOfLIS(vector<int>& nums) {
    vector<int> tails;
    for (int num : nums) {
        auto it = lower_bound(tails.begin(), tails.end(), num);
        if (it == tails.end()) {
            tails.push_back(num);
        } else {
            *it = num;
        }
    }
    return tails.size();
}

4.3 最长严格递增子序列 ​

cpp
int lengthOfLISStrict(vector<int>& nums) {
    vector<int> tails;
    for (int num : nums) {
        auto it = lower_bound(tails.begin(), tails.end(), num);
        if (it == tails.end()) {
            tails.push_back(num);
        } else {
            *it = num;
        }
    }
    return tails.size();
}

五、滚动数组优化 ​

5.1 一维滚动数组 ​

cpp
// 优化前
int fibonacci(int n) {
    vector<int> dp(n + 1);
    dp[0] = 0; dp[1] = 1;
    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i-1] + dp[i-2];
    }
    return dp[n];
}

// 优化后
int fibonacci(int n) {
    if (n <= 1) return n;
    int prev2 = 0, prev1 = 1;
    for (int i = 2; i <= n; i++) {
        int curr = prev1 + prev2;
        prev2 = prev1;
        prev1 = curr;
    }
    return prev1;
}

5.2 二维滚动数组 ​

cpp
// 优化前
int uniquePaths(int m, int n) {
    vector<vector<int>> dp(m, vector<int>(n, 1));
    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            dp[i][j] = dp[i-1][j] + dp[i][j-1];
        }
    }
    return dp[m-1][n-1];
}

// 优化后
int uniquePaths(int m, int n) {
    vector<int> dp(n, 1);
    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            dp[j] += dp[j-1];
        }
    }
    return dp[n-1];
}

六、状态压缩动态规划 ​

6.1 状态压缩概述 ​

状态压缩DP使用二进制数来表示状态，适用于状态数量较少的问题。

6.2 旅行商问题(TSP) ​

cpp
int tsp(vector<vector<int>>& graph) {
    int n = graph.size();
    int full_mask = (1 << n) - 1;
    vector<vector<int>> dp(n, vector<int>(1 << n, INT_MAX));
    
    dp[0][1] = 0; // 从0出发
    
    for (int mask = 1; mask <= full_mask; mask++) {
        for (int u = 0; u < n; u++) {
            if (!(mask & (1 << u))) continue;
            for (int v = 0; v < n; v++) {
                if (mask & (1 << v)) continue;
                int new_mask = mask | (1 << v);
                dp[v][new_mask] = min(dp[v][new_mask], dp[u][mask] + graph[u][v]);
            }
        }
    }
    
    int min_cost = INT_MAX;
    for (int u = 1; u < n; u++) {
        min_cost = min(min_cost, dp[u][full_mask] + graph[u][0]);
    }
    return min_cost;
}

百炼成钢，融会贯通

© 2026 百练百会（bestwit）GESP备考一站式平台 | 京ICP备16040576号-5