常见动态规划类型--案例详解

在面试中，好多题都会用到动态规划，系统性的学习动态规划，其重要性不言而喻。

动态规划的核心思想是将原问题拆解成子问题，并通过解决子问题来求解原问题。为了避免重复计算，动态规划会将子问题的解进行存储，在需要的时候直接获取，从而提高效率。

动态规划通常适用于满足两个要素的问题：

1. 重叠子问题： 原问题可以分解成子问题，且这些子问题在解空间中有重叠，即同一个子问题会被多次求解。
2. 最优子结构： 原问题的最优解可以通过子问题的最优解来构造。

动态规划的解题步骤：

以计算斐波那契数列为例进行说明。斐波那契数列的定义是：F(0) = 0，F(1) = 1，对于每个 n ≥ 2，F(n) = F(n-1) + F(n-2)。

1. 定义状态： 确定问题的状态，即原问题和子问题中变化的变量。例如，在计算斐波那契数列问题中，定义状态 dpi 表示第 i 个斐波那契数。
2. 找到状态转移方程： 确定问题状态之间的转移关系，即从一个状态到另一个状态的过程。例如，在计算斐波那契数列问题中，dpi = dpi-1 + dpi-2，即第 i 个斐波那契数等于前两个斐波那契数的和。
3. 初始化： 初始化状态的初始值，通常是边界情况，用于保证状态转移的正确性。例如，在计算斐波那契数列问题中，初始化 dp0 = 0，dp1 = 1，因为斐波那契数列的前两项是已知的。
4. 计算顺序： 按照一定的计算顺序，通常是从小规模的子问题逐步求解到原问题。例如，在计算斐波那契数列问题中，这从 i = 2 开始，依次计算 dp2、dp3，直到 dpn。
5. 求解原问题： 根据状态转移方程和已计算的子问题解，求解原问题的最优解。例如，在计算斐波那契数列问题中，返回 dpn 即为所求的第 n 个斐波那契数。

代码实现如下

public int fib(int n) {
    if (n <= 1) {
        return n;
    }

    int[] dp = new int[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];
}

在这个例子中，dpi 表示第 i 个斐波那契数，通过循环计算并填充 dp 数组，最终返回 dpn 即为第 n 个斐波那契数。。

动态规划问题分类

常见类型的动态规划问题可以分为一下几类：

1. 线性动态规划： 问题可以表示为一维数组的状态，例如斐波那契数列。
2. 区间动态规划： 问题涉及对区间进行划分和计算，例如最长回文子序列。
3. 背包问题： 问题涉及在限定容量下选择不同的物品以最大化或最小化某个值，例如0/1背包问题。
4. 最短路径问题： 问题涉及寻找两点之间的最短路径，例如Floyd-Warshall算法。
5. 树形动态规划： 问题涉及树结构的遍历和计算，例如在树上求解最长路径。

线性动态规划

一个经典的线性动态规划问题是最长递增子序列。问题是找到给定数组中的最长递增子序列的长度。

解题步骤

1. 定义状态：定义状态 dpi 表示以第 i 个元素为结尾的最长递增子序列的长度。
2. 找到状态转移方程：dpi 的值可以通过比较第 i 个元素与前面所有元素的关系得到，如果 numsi 大于某个元素 numsj，则 dpi = max(dpi, dpj + 1)。
3. 初始化：将所有 dpi 初始化为1，因为每个元素本身都是一个递增子序列。
4. 计算顺序：从左到右遍历数组，对于每个元素，再从数组的开头到该元素，更新 dpi 的值。
5. 求解原问题：最终，原问题的解就是 dp 数组中的最大值。

代码实现

public static int lengthOfLIS(int[] nums) {
    if (nums == null || nums.length == 0) {
        return 0;
    }

    int n = nums.length;
    int[] dp = new int[n];
    Arrays.fill(dp, 1);

    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (nums[i] > nums[j]) {
                dp[i] = Math.max(dp[i], dp[j] + 1);
            }
        }
    }

    int maxLength = 1;
    for (int length : dp) {
        maxLength = Math.max(maxLength, length);
    }

    return maxLength;
}

在这个例子中，dpi 表示以第 i 个元素为结尾的最长递增子序列的长度，通过循环计算并填充 dp 数组，最终返回 dpn 即为最长递增子序列的长度。

区间动态规划

一个经典的区间动态规划问题是最长回文子序列。

问题：找到给定字符串中的最长回文子序列的长度。

解题步骤

1. 定义状态：定义状态 dpi 表示字符串从第 i 个字符到第 j 个字符之间的最长回文子序列的长度。
2. 找到状态转移方程：如果 si == sj，则 dpi = dpi+1 + 2，因为两端的字符相等，可以加上这两个字符构成更长的回文子序列。如果 si != sj，则 dpi = max(dpi+1, dpi)，取两种情况中的最大值。
3. 初始化：对角线上的元素初始化为1，即 dpi = 1，表示单个字符是回文子序列。
4. 计算顺序：从下到上、从左到右的顺序填充 dp 数组。
5. 求解原问题：返回 dp0，其中 n 是字符串的长度，即为整个字符串的最长回文子序列的长度。

代码实现

public static int longestPalindromeSubseq(String s) {
    int n = s.length();
    int[][] dp = new int[n][n];

    // 初始化：单个字符是回文子序列
    for (int i = 0; i < n; i++) {
        dp[i][i] = 1;
    }

    // 计算顺序
    for (int len = 2; len <= n; len++) {
        for (int i = 0; i <= n - len; i++) {
            int j = i + len - 1;
            if (s.charAt(i) == s.charAt(j)) {
                dp[i][j] = dp[i + 1][j - 1] + 2;
            } else {
                dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
            }
        }
    }
    // 求解原问题
    return dp[0][n - 1];
}

在这个例子中，dpi 表示字符串从第 i 个字符到第 j 个字符之间的最长回文子序列的长度，通过填充 dp 数组，最终返回 dp0 即为整个字符串的最长回文子序列的长度。

背包问题

一个经典的背包问题是0/1背包问题。

问题：给定一组物品，每个物品有自己的重量和价值，同时给定一个固定的背包容量，目标是选择一些物品装入背包中，使得装入的物品的总价值最大，且不能超过背包的容量。

解题步骤

1. 定义状态：定义状态 dpi 表示在前 i 个物品中选择一些物品，使得它们的总重量不超过 w 时的最大总价值。
2. 找到状态转移方程：dpi 的值可以通过比较两种情况得到：选择第 i 个物品和不选择第 i 个物品。如果选择第 i 个物品，dpi = dpi-1w - weighti] + valuei，否则 dpi = dpi-1。
3. 初始化：初始化 dp0 = 0 和 dpi = 0，表示在背包容量为0时或者没有物品可选时，总价值为0。
4. 计算顺序：从 i = 1 到 n，从 w = 1 到 W，按照状态转移方程计算 dpi。
5. 求解原问题：返回 dpn，其中 n 是物品的数量，W 是背包的容量，即为问题的最优解。

代码实现

public static int knapsack(int[] weights, int[] values, int capacity) {
    int n = weights.length;
    int[][] dp = new int[n + 1][capacity + 1];

    // 计算顺序
    for (int i = 1; i <= n; i++) {
        for (int w = 1; w <= capacity; w++) {
            if (weights[i - 1] <= w) {
                dp[i][w] = Math.max(dp[i - 1][w], values[i - 1] + dp[i - 1][w - weights[i - 1]]);
            } else {
                dp[i][w] = dp[i - 1][w];
            }
        }
    }
    // 求解原问题
    return dp[n][capacity];
}

在这个例子中，dpi 表示在前 i 个物品中选择一些物品，使得它们的总重量不超过 w 时的最大总价值，通过填充 dp 数组，最终返回 dpn 即为问题的最优解。

最短路径问题

一个经典的最短路径问题是Floyd-Warshall算法，它用于寻找图中所有节点对之间的最短路径。

问题：给定一个有向图，每条边都有一个权重，找到每一对节点之间的最短路径。

解题步骤

1. 定义状态：定义状态 disti 表示节点 i 到节点 j 的最短路径长度。
2. 找到状态转移方程：Floyd-Warshall算法采用三重循环，对于每一对节点 i 和 j，检查是否存在一个节点 k 使得通过 k 路径到达 j 比直接到达 j 的路径更短：disti = min(disti, disti + distk)。
3. 初始化：初始化 disti 为直接相连的边的权重，如果没有直接相连的边，则初始化为一个表示无穷大的值。
4. 计算顺序：三重循环嵌套，外层循环遍历所有节点 k，中间循环遍历所有节点 i，内层循环遍历所有节点 j，按照状态转移方程更新 disti。
5. 求解原问题：返回 dist 数组，其中 disti 表示节点 i 到节点 j 的最短路径长度。

代码实现

public static int[][] floydWarshall(int[][] graph, int V) {
    int[][] dist = new int[V][V];

    // 初始化
    for (int i = 0; i < V; i++) {
        for (int j = 0; j < V; j++) {
            dist[i][j] = graph[i][j];
        }
    }

    // 计算顺序
    for (int k = 0; k < V; k++) {
        for (int i = 0; i < V; i++) {
            for (int j = 0; j < V; j++) {
                if (dist[i][k] != Integer.MAX_VALUE && dist[k][j] != Integer.MAX_VALUE &&
                    dist[i][k] + dist[k][j] < dist[i][j]) {
                    dist[i][j] = dist[i][k] + dist[k][j];
                }
            }
        }
    }

    // 求解原问题
    return dist;
} 

在这个例子中，disti 表示节点 i 到节点 j 的最短路径长度，通过三重循环嵌套更新 dist 数组，最终返回 dist 数组即为问题的最优解。

我正在参与2023腾讯技术创作特训营第三期有奖征文，组队打卡瓜分大奖！