动态规划算法：最优化问题的递推求解

算法原理

动态规划（Dynamic Programming, DP）是一种通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。它适用于有重叠子问题和最优子结构性质的问题，通过存储子问题的解来避免重复计算。

基本思想

1. 状态定义：确定问题的状态表示
2. 状态转移：找到状态之间的递推关系
3. 边界条件：确定初始状态和边界情况
4. 求解顺序：确定计算状态的顺序
5. 优化存储：根据需要优化空间复杂度

核心特征

1. 最优子结构：问题的最优解包含子问题的最优解
2. 重叠子问题：递归过程中出现相同的子问题
3. 无后效性：当前状态的未来发展只依赖当前状态

优缺点分析

优点

1. 避免重复计算：通过存储中间结果提高效率
2. 思路清晰：将复杂问题分解为简单子问题
3. 最优性保证：能找到全局最优解
4. 应用广泛：适用于多种优化问题

缺点

1. 空间复杂度高：需要存储大量中间状态
2. 状态设计困难：需要正确定义状态和转移
3. 维度爆炸：多维DP的空间复杂度增长很快
4. 不易理解：递推关系可能比较抽象

使用场景

适用场景

1. 最优化问题：最短路径、最大利润等
2. 计数问题：方案数、排列组合数
3. 决策问题：背包问题、股票交易
4. 序列问题：最长公共子序列、编辑距离
5. 区间问题：矩阵链乘法、回文检测

C语言实现

经典DP问题实现

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

#define MAX_N 1000
#define MAX_W 10000
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))

/**
 * 1. 斐波那契数列（入门级DP）
 */
long long fibonacci_dp(int n) {
    if (n <= 1) return n;
    
    long long* dp = (long long*)malloc((n + 1) * sizeof(long long));
    dp[0] = 0;
    dp[1] = 1;
    
    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i-1] + dp[i-2];
    }
    
    long long result = dp[n];
    free(dp);
    return result;
}

// 空间优化版本
long long fibonacci_optimized(int n) {
    if (n <= 1) return n;
    
    long long prev2 = 0, prev1 = 1;
    for (int i = 2; i <= n; i++) {
        long long current = prev1 + prev2;
        prev2 = prev1;
        prev1 = current;
    }
    return prev1;
}

/**
 * 2. 0-1背包问题
 */
int knapsack_01(int weights[], int values[], int n, int capacity) {
    // dp[i][w] 表示前i个物品在容量为w时的最大价值
    int** dp = (int**)malloc((n + 1) * sizeof(int*));
    for (int i = 0; i <= n; i++) {
        dp[i] = (int*)calloc(capacity + 1, sizeof(int));
    }
    
    for (int i = 1; i <= n; i++) {
        for (int w = 1; w <= capacity; w++) {
            // 不选择第i个物品
            dp[i][w] = dp[i-1][w];
            
            // 选择第i个物品（如果容量允许）
            if (weights[i-1] <= w) {
                dp[i][w] = max(dp[i][w], 
                              dp[i-1][w - weights[i-1]] + values[i-1]);
            }
        }
    }
    
    int result = dp[n][capacity];
    
    // 回溯找到选择的物品
    printf("选择的物品: ");
    int w = capacity;
    for (int i = n; i > 0 && w > 0; i--) {
        if (dp[i][w] != dp[i-1][w]) {
            printf("%d ", i-1);
            w -= weights[i-1];
        }
    }
    printf("\n");
    
    // 释放内存
    for (int i = 0; i <= n; i++) {
        free(dp[i]);
    }
    free(dp);
    
    return result;
}

// 空间优化的0-1背包
int knapsack_01_optimized(int weights[], int values[], int n, int capacity) {
    int* dp = (int*)calloc(capacity + 1, sizeof(int));
    
    for (int i = 0; i < n; i++) {
        // 从右到左更新，避免重复使用
        for (int w = capacity; w >= weights[i]; w--) {
            dp[w] = max(dp[w], dp[w - weights[i]] + values[i]);
        }
    }
    
    int result = dp[capacity];
    free(dp);
    return result;
}

/**
 * 3. 最长公共子序列（LCS）
 */
int lcs_length(char* str1, char* str2) {
    int m = strlen(str1);
    int n = strlen(str2);
    
    int** dp = (int**)malloc((m + 1) * sizeof(int*));
    for (int i = 0; i <= m; i++) {
        dp[i] = (int*)calloc(n + 1, sizeof(int));
    }
    
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (str1[i-1] == str2[j-1]) {
                dp[i][j] = dp[i-1][j-1] + 1;
            } else {
                dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
            }
        }
    }
    
    // 构造LCS字符串
    char* lcs = (char*)malloc((dp[m][n] + 1) * sizeof(char));
    int index = dp[m][n];
    lcs[index] = '\0';
    
    int i = m, j = n;
    while (i > 0 && j > 0) {
        if (str1[i-1] == str2[j-1]) {
            lcs[--index] = str1[i-1];
            i--; j--;
        } else if (dp[i-1][j] > dp[i][j-1]) {
            i--;
        } else {
            j--;
        }
    }
    
    printf("最长公共子序列: %s\n", lcs);
    
    int result = dp[m][n];
    
    // 清理内存
    for (int i = 0; i <= m; i++) {
        free(dp[i]);
    }
    free(dp);
    free(lcs);
    
    return result;
}

/**
 * 4. 编辑距离（莱文斯坦距离）
 */
int edit_distance(char* str1, char* str2) {
    int m = strlen(str1);
    int n = strlen(str2);
    
    int** dp = (int**)malloc((m + 1) * sizeof(int*));
    for (int i = 0; i <= m; i++) {
        dp[i] = (int*)malloc((n + 1) * sizeof(int));
    }
    
    // 初始化边界条件
    for (int i = 0; i <= m; i++) dp[i][0] = i;
    for (int j = 0; j <= n; j++) dp[0][j] = j;
    
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (str1[i-1] == str2[j-1]) {
                dp[i][j] = dp[i-1][j-1];
            } else {
                dp[i][j] = 1 + min(min(dp[i-1][j],    // 删除
                                       dp[i][j-1]),   // 插入
                                       dp[i-1][j-1]); // 替换
            }
        }
    }
    
    int result = dp[m][n];
    
    for (int i = 0; i <= m; i++) {
        free(dp[i]);
    }
    free(dp);
    
    return result;
}

/**
 * 5. 最长递增子序列（LIS）
 */
int longest_increasing_subsequence(int arr[], int n) {
    int* dp = (int*)malloc(n * sizeof(int));
    int* parent = (int*)malloc(n * sizeof(int));
    
    // 初始化
    for (int i = 0; i < n; i++) {
        dp[i] = 1;
        parent[i] = -1;
    }
    
    int max_length = 1;
    int max_index = 0;
    
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (arr[j] < arr[i] && dp[j] + 1 > dp[i]) {
                dp[i] = dp[j] + 1;
                parent[i] = j;
            }
        }
        
        if (dp[i] > max_length) {
            max_length = dp[i];
            max_index = i;
        }
    }
    
    // 构造LIS
    int* lis = (int*)malloc(max_length * sizeof(int));
    int current = max_index;
    for (int i = max_length - 1; i >= 0; i--) {
        lis[i] = arr[current];
        current = parent[current];
    }
    
    printf("最长递增子序列: ");
    for (int i = 0; i < max_length; i++) {
        printf("%d ", lis[i]);
    }
    printf("\n");
    
    free(dp);
    free(parent);
    free(lis);
    
    return max_length;
}

/**
 * 6. 硬币找零问题
 */
int coin_change(int coins[], int n, int amount) {
    int* dp = (int*)malloc((amount + 1) * sizeof(int));
    
    // 初始化：除了0需要0个硬币，其他都设为无穷大
    dp[0] = 0;
    for (int i = 1; i <= amount; i++) {
        dp[i] = INT_MAX;
    }
    
    for (int i = 1; i <= amount; i++) {
        for (int j = 0; j < n; j++) {
            if (coins[j] <= i && dp[i - coins[j]] != INT_MAX) {
                dp[i] = min(dp[i], dp[i - coins[j]] + 1);
            }
        }
    }
    
    int result = (dp[amount] == INT_MAX) ? -1 : dp[amount];
    free(dp);
    return result;
}

/**
 * 7. 矩阵链乘法
 */
int matrix_chain_multiplication(int dimensions[], int n) {
    // dp[i][j] 表示从矩阵i到矩阵j的最小乘法次数
    int** dp = (int**)malloc(n * sizeof(int*));
    for (int i = 0; i < n; i++) {
        dp[i] = (int*)calloc(n, sizeof(int));
    }
    
    // l是链的长度
    for (int l = 2; l < n; l++) {
        for (int i = 1; i < n - l + 1; i++) {
            int j = i + l - 1;
            dp[i][j] = INT_MAX;
            
            for (int k = i; k <= j - 1; k++) {
                int cost = dp[i][k] + dp[k+1][j] + 
                          dimensions[i-1] * dimensions[k] * dimensions[j];
                dp[i][j] = min(dp[i][j], cost);
            }
        }
    }
    
    int result = dp[1][n-1];
    
    for (int i = 0; i < n; i++) {
        free(dp[i]);
    }
    free(dp);
    
    return result;
}

/**
 * 8. 回文子串检测
 */
void palindrome_substrings(char* str) {
    int n = strlen(str);
    bool** dp = (bool**)malloc(n * sizeof(bool*));
    for (int i = 0; i < n; i++) {
        dp[i] = (bool*)calloc(n, sizeof(bool));
    }
    
    int count = 0;
    
    // 长度为1的子串都是回文
    for (int i = 0; i < n; i++) {
        dp[i][i] = true;
        count++;
    }
    
    // 长度为2的子串
    for (int i = 0; i < n - 1; i++) {
        if (str[i] == str[i + 1]) {
            dp[i][i + 1] = true;
            count++;
        }
    }
    
    // 长度大于2的子串
    for (int len = 3; len <= n; len++) {
        for (int i = 0; i < n - len + 1; i++) {
            int j = i + len - 1;
            if (str[i] == str[j] && dp[i + 1][j - 1]) {
                dp[i][j] = true;
                count++;
            }
        }
    }
    
    printf("回文子串总数: %d\n", count);
    
    for (int i = 0; i < n; i++) {
        free(dp[i]);
    }
    free(dp);
}

/**
 * 9. 股票买卖问题（含冷冻期）
 */
int stock_with_cooldown(int prices[], int n) {
    if (n <= 1) return 0;
    
    int* hold = (int*)malloc(n * sizeof(int));    // 持有股票
    int* sold = (int*)malloc(n * sizeof(int));    // 刚卖出股票
    int* rest = (int*)malloc(n * sizeof(int));    // 冷冻期
    
    hold[0] = -prices[0];
    sold[0] = 0;
    rest[0] = 0;
    
    for (int i = 1; i < n; i++) {
        hold[i] = max(hold[i-1], rest[i-1] - prices[i]);
        sold[i] = hold[i-1] + prices[i];
        rest[i] = max(rest[i-1], sold[i-1]);
    }
    
    int result = max(sold[n-1], rest[n-1]);
    
    free(hold);
    free(sold);
    free(rest);
    
    return result;
}

/**
 * 10. 分割回文串II
 */
int min_cut_palindrome(char* str) {
    int n = strlen(str);
    
    // 预处理：检查所有子串是否为回文
    bool** is_palindrome = (bool**)malloc(n * sizeof(bool*));
    for (int i = 0; i < n; i++) {
        is_palindrome[i] = (bool*)calloc(n, sizeof(bool));
    }
    
    for (int len = 1; len <= n; len++) {
        for (int i = 0; i <= n - len; i++) {
            int j = i + len - 1;
            if (len == 1) {
                is_palindrome[i][j] = true;
            } else if (len == 2) {
                is_palindrome[i][j] = (str[i] == str[j]);
            } else {
                is_palindrome[i][j] = (str[i] == str[j] && is_palindrome[i+1][j-1]);
            }
        }
    }
    
    // DP求最小分割数
    int* dp = (int*)malloc(n * sizeof(int));
    for (int i = 0; i < n; i++) {
        dp[i] = i; // 最坏情况：每个字符都分割
        
        if (is_palindrome[0][i]) {
            dp[i] = 0;
        } else {
            for (int j = 0; j < i; j++) {
                if (is_palindrome[j+1][i]) {
                    dp[i] = min(dp[i], dp[j] + 1);
                }
            }
        }
    }
    
    int result = dp[n-1];
    
    for (int i = 0; i < n; i++) {
        free(is_palindrome[i]);
    }
    free(is_palindrome);
    free(dp);
    
    return result;
}

// 测试函数
void test_fibonacci() {
    printf("=== 斐波那契数列测试 ===\n");
    for (int i = 0; i <= 10; i++) {
        printf("F(%d) = %lld\n", i, fibonacci_dp(i));
    }
    printf("\n");
}

void test_knapsack() {
    printf("=== 背包问题测试 ===\n");
    int weights[] = {2, 1, 3, 2};
    int values[] = {12, 10, 20, 15};
    int n = 4;
    int capacity = 5;
    
    printf("物品重量: ");
    for (int i = 0; i < n; i++) printf("%d ", weights[i]);
    printf("\n物品价值: ");
    for (int i = 0; i < n; i++) printf("%d ", values[i]);
    printf("\n背包容量: %d\n", capacity);
    
    int max_value = knapsack_01(weights, values, n, capacity);
    printf("最大价值: %d\n\n", max_value);
}

void test_lcs() {
    printf("=== 最长公共子序列测试 ===\n");
    char str1[] = "ABCDGH";
    char str2[] = "AEDFHR";
    
    printf("字符串1: %s\n", str1);
    printf("字符串2: %s\n", str2);
    
    int length = lcs_length(str1, str2);
    printf("LCS长度: %d\n\n", length);
}

void test_edit_distance() {
    printf("=== 编辑距离测试 ===\n");
    char str1[] = "sunday";
    char str2[] = "saturday";
    
    printf("字符串1: %s\n", str1);
    printf("字符串2: %s\n", str2);
    
    int distance = edit_distance(str1, str2);
    printf("编辑距离: %d\n\n", distance);
}

void test_lis() {
    printf("=== 最长递增子序列测试 ===\n");
    int arr[] = {10, 9, 2, 5, 3, 7, 101, 18};
    int n = sizeof(arr) / sizeof(arr[0]);
    
    printf("数组: ");
    for (int i = 0; i < n; i++) printf("%d ", arr[i]);
    printf("\n");
    
    int length = longest_increasing_subsequence(arr, n);
    printf("LIS长度: %d\n\n", length);
}

int main() {
    test_fibonacci();
    test_knapsack();
    test_lcs();
    test_edit_distance();
    test_lis();
    
    return 0;
}

复杂度分析

时间复杂度

• 一维DP：通常为O(n)或O(n²)
• 二维DP：通常为O(n²)或O(nm)
• 具体取决于：状态数量和转移复杂度

空间复杂度

• 朴素实现：等于状态数量
• 滚动数组优化：可降到O(1)或O(n)
• 记忆化搜索：递归栈深度

实际应用

1. 算法竞赛：各种DP问题
2. 机器学习：神经网络训练
3. 生物信息学：序列比对
4. 经济学：最优决策问题
5. 工程优化：资源分配

总结

动态规划是解决最优化问题的重要方法，其核心在于将复杂问题分解为子问题，并通过存储子问题的解避免重复计算。掌握动态规划需要大量练习来培养状态设计和转移方程的直觉，是算法学习中的重要里程碑。

版权所有，如有侵权请联系我