在面试中,好多题都会用到动态规划,系统性的学习动态规划,其重要性不言而喻。
动态规划的核心思想是将原问题拆解成子问题,并通过解决子问题来求解原问题。为了避免重复计算,动态规划会将子问题的解进行存储,在需要的时候直接获取,从而提高效率。
动态规划通常适用于满足两个要素的问题:
以计算斐波那契数列为例进行说明。斐波那契数列的定义是:F(0) = 0,F(1) = 1,对于每个 n ≥ 2,F(n) = F(n-1) + F(n-2)。
代码实现如下
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 个斐波那契数。。
常见类型的动态规划问题可以分为一下几类:
一个经典的线性动态规划问题是最长递增子序列。问题是找到给定数组中的最长递增子序列的长度。
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 即为最长递增子序列的长度。
一个经典的区间动态规划问题是最长回文子序列。
问题:找到给定字符串中的最长回文子序列的长度。
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背包问题。
问题:给定一组物品,每个物品有自己的重量和价值,同时给定一个固定的背包容量,目标是选择一些物品装入背包中,使得装入的物品的总价值最大,且不能超过背包的容量。
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算法,它用于寻找图中所有节点对之间的最短路径。
问题:给定一个有向图,每条边都有一个权重,找到每一对节点之间的最短路径。
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 数组即为问题的最优解。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。