在面试中，好多题都会用到动态规划，系统性的学习动态规划，其重要性不言而喻。
动态规划的核心思想是将原问题拆解成子问题，并通过解决子问题来求解原问题。为了避免重复计算，动态规划会将子问题的解进行存储，在需要的时候直接获取，从而提高效率。
动态规划通常适用于满足两个要素的问题：
- 重叠子问题： 原问题可以分解成子问题，且这些子问题在解空间中有重叠，即同一个子问题会被多次求解。
- 最优子结构： 原问题的最优解可以通过子问题的最优解来构造。
动态规划的解题步骤：
以计算斐波那契数列为例进行说明。斐波那契数列的定义是：F(0) = 0，F(1) = 1，对于每个 n ≥ 2，F(n) = F(n-1) F(n-2)。
- 定义状态： 确定问题的状态，即原问题和子问题中变化的变量。例如，在计算斐波那契数列问题中，定义状态 dpi 表示第 i 个斐波那契数。
- 找到状态转移方程： 确定问题状态之间的转移关系，即从一个状态到另一个状态的过程。例如，在计算斐波那契数列问题中，dpi = dpi-1 dpi-2，即第 i 个斐波那契数等于前两个斐波那契数的和。
- 初始化： 初始化状态的初始值，通常是边界情况，用于保证状态转移的正确性。例如，在计算斐波那契数列问题中，初始化 dp0 = 0，dp1 = 1，因为斐波那契数列的前两项是已知的。
- 计算顺序： 按照一定的计算顺序，通常是从小规模的子问题逐步求解到原问题。例如，在计算斐波那契数列问题中，这从 i = 2 开始，依次计算 dp2、dp3，直到 dpn。
- 求解原问题： 根据状态转移方程和已计算的子问题解，求解原问题的最优解。例如，在计算斐波那契数列问题中，返回 dpn 即为所求的第 n 个斐波那契数。
代码实现如下
代码语言：java复制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 个斐波那契数。。
动态规划问题分类
常见类型的动态规划问题可以分为一下几类：
- 线性动态规划： 问题可以表示为一维数组的状态，例如斐波那契数列。
- 区间动态规划： 问题涉及对区间进行划分和计算，例如最长回文子序列。
- 背包问题： 问题涉及在限定容量下选择不同的物品以最大化或最小化某个值，例如0/1背包问题。
- 最短路径问题： 问题涉及寻找两点之间的最短路径，例如Floyd-Warshall算法。
- 树形动态规划： 问题涉及树结构的遍历和计算，例如在树上求解最长路径。
线性动态规划
一个经典的线性动态规划问题是最长递增子序列。问题是找到给定数组中的最长递增子序列的长度。
解题步骤
- 定义状态：定义状态 dpi 表示以第 i 个元素为结尾的最长递增子序列的长度。
- 找到状态转移方程：dpi 的值可以通过比较第 i 个元素与前面所有元素的关系得到，如果 numsi 大于某个元素 numsj，则 dpi = max(dpi, dpj 1)。
- 初始化：将所有 dpi 初始化为1，因为每个元素本身都是一个递增子序列。
- 计算顺序：从左到右遍历数组，对于每个元素，再从数组的开头到该元素，更新 dpi 的值。
- 求解原问题：最终，原问题的解就是 dp 数组中的最大值。
代码实现
代码语言：java复制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 即为最长递增子序列的长度。
区间动态规划
一个经典的区间动态规划问题是最长回文子序列。
问题：找到给定字符串中的最长回文子序列的长度。
解题步骤
- 定义状态：定义状态 dpi 表示字符串从第 i 个字符到第 j 个字符之间的最长回文子序列的长度。
- 找到状态转移方程：如果 si == sj，则 dpi = dpi 1 2，因为两端的字符相等，可以加上这两个字符构成更长的回文子序列。如果 si != sj，则 dpi = max(dpi 1, dpi)，取两种情况中的最大值。
- 初始化：对角线上的元素初始化为1，即 dpi = 1，表示单个字符是回文子序列。
- 计算顺序：从下到上、从左到右的顺序填充 dp 数组。
- 求解原问题：返回 dp0，其中 n 是字符串的长度，即为整个字符串的最长回文子序列的长度。
代码实现
代码语言：java复制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背包问题。
问题：给定一组物品，每个物品有自己的重量和价值，同时给定一个固定的背包容量，目标是选择一些物品装入背包中，使得装入的物品的总价值最大，且不能超过背包的容量。
解题步骤
- 定义状态：定义状态 dpi 表示在前 i 个物品中选择一些物品，使得它们的总重量不超过 w 时的最大总价值。
- 找到状态转移方程：dpi 的值可以通过比较两种情况得到：选择第 i 个物品和不选择第 i 个物品。如果选择第 i 个物品，dpi = dpi-1w - weighti] valuei，否则 dpi = dpi-1。
- 初始化：初始化 dp0 = 0 和 dpi = 0，表示在背包容量为0时或者没有物品可选时，总价值为0。
- 计算顺序：从 i = 1 到 n，从 w = 1 到 W，按照状态转移方程计算 dpi。
- 求解原问题：返回 dpn，其中 n 是物品的数量，W 是背包的容量，即为问题的最优解。
代码实现
代码语言：java复制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算法，它用于寻找图中所有节点对之间的最短路径。
问题：给定一个有向图，每条边都有一个权重，找到每一对节点之间的最短路径。
解题步骤
- 定义状态：定义状态 disti 表示节点 i 到节点 j 的最短路径长度。
- 找到状态转移方程：Floyd-Warshall算法采用三重循环，对于每一对节点 i 和 j，检查是否存在一个节点 k 使得通过 k 路径到达 j 比直接到达 j 的路径更短：disti = min(disti, disti distk)。
- 初始化：初始化 disti 为直接相连的边的权重，如果没有直接相连的边，则初始化为一个表示无穷大的值。
- 计算顺序：三重循环嵌套，外层循环遍历所有节点 k，中间循环遍历所有节点 i，内层循环遍历所有节点 j，按照状态转移方程更新 disti。
- 求解原问题：返回 dist 数组，其中 disti 表示节点 i 到节点 j 的最短路径长度。
代码实现
代码语言：java复制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腾讯技术创作特训营第三期有奖征文，组队打卡瓜分大奖！
