0%

常用算法总结之动态规划

动态规划算法思想

动态规划(dynamic programming)与分治方法相似,都是通过组合子问题的解来求解原问题(在这里,programming 指的是一种表格法)。分治法将问题划分为互不相交的子问题,再将他们的解组合起来,求出原问题的解。与之相反,动态规划应用于子问题重叠的情况,即不同的子问题具有公共的子问题(子问题的求解释递归进行的,将其划分为更小的子子问题)。在这种情况下,分治法会做许多不必要的工作,它会反复求解那些公共子问题。而动态规划算法对每个子问题只求解一次,将其解保存在一个表格中,从而无需每次求解一个子问题时都重新计算,避免了这种不必要的计算工作。

适用场景

动态规划方法通常用来求解最优化问题。这类问题可以有很多可行解,每个解都有一个值,我们希望寻找具有最优值(最小值或最大值)的解。我们称这样的解为问题的一个最优解(an optimal solution),而不是最优解(the optimal solution),因为可能有多个解都达到最优值。

设计动态规划算法的步骤

我们通常按如下4个步骤来设计一个动态规划算法:

  1. 刻画一个最优解的结构特征
  2. 递归地定义最优解的值
  3. 计算最优解的值,通常采用自底向上的方法
  4. 利用计算出的信息构造一个最优解

步骤1~3是动态规划算法求解问题的基础。如果我们仅仅需要一个最优解的值,而非解本身,可以忽略步骤4.如果确实要做步骤4,有时就需要步骤3的过程中维护一些额外信息,以便用来构造一个最优解。

最长公共子序列问题

leetcode 583. Delete Operation for Two Strings

基本解法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
public static int minDistance(String word1, String word2) {
int len1 = word1.length();
int len2 = word2.length();
if (len1 == 0) {
return len2;
}
if (len2 == 0) {
return len1;
}

// 二维数组可用 一位数组 + 临时一位数组 替换掉
int[][] dp = new int[len1][len2];
dp[0][0] = word1.charAt(0) == word2.charAt(0) ? 1 : 0;

for (int i = 1; i < len1; i++) {
if (dp[i - 1][0] == 1 || word1.charAt(i) == word2.charAt(0)) {
dp[i][0] = 1;
}
}

for (int j = 1; j < len2; j++) {
if (dp[0][j - 1] == 1 || word1.charAt(0) == word2.charAt(j)) {
dp[0][j] = 1;
}
}

for (int i = 1; i < len1; i++) {
for (int j = 1; j < len2; j++) {
// 此处赋值语句可优化
// dp[i - 1][j - 1] + 1 >= Math.max(dp[i - 1][j], dp[i][j - 1])
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
if (word1.charAt(i) == word2.charAt(j)) {
dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - 1] + 1);
}
}
}
// for (int i = 0; i < dp.length; i++) {
// System.out.println(Arrays.toString(dp[i]));
// }

return len1 - dp[len1 - 1][len2 - 1] + len2 - dp[len1 - 1][len2 - 1];

优化解法:

  • 借用临时数组temp,将二维dp数组降维
  • 优化赋值判断逻辑
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    public static int minDistanceDpQuick(String word1, String word2) {
    int len1 = word1.length();
    int len2 = word2.length();

    // 使用一维数组
    int[] dp = new int[len2 + 1];

    for (int i = 0; i < len1; i++) {
    // 借用临时数组temp,将二维dp数组降维
    int[] temp = new int[len2 + 1];
    for (int j = 0; j < len2; j++) {
    // 优化基本解法的 赋值逻辑
    if (word1.charAt(i) == word2.charAt(j)) {
    temp[j + 1] = Math.max(temp[j + 1], dp[j] + 1);
    } else {
    temp[j + 1] = Math.max(dp[j + 1], temp[j]);
    }
    }
    dp = temp;
    }

    return len1 - dp[len2] + len2 - dp[len2];
    }

最长公共子串问题

leetcode 718. Maximum Length of Repeated Subarray

基本解法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
public static int findLength(int[] A, int[] B) {
if (A.length == 0 || B.length == 0) {
return 0;
}

int[][] dp = new int[A.length][B.length];

dp[0][0] = A[0] == B[0] ? 1 : 0;

int result = dp[0][0];

for (int i = 1; i < B.length; i++) {
if (A[0] == B[i]) {
dp[0][i] = 1;
if (dp[0][i] > result) {
result = dp[0][i];
}
} else {
dp[0][i] = 0;
}
}

for (int i = 1; i < A.length; i++) {
if (A[i] == B[0]) {
dp[i][0] = 1;
if (dp[i][0] > result) {
result = dp[i][0];
}
} else {
dp[i][0] = 0;
}
}

for (int i = 1; i < A.length; i++) {
for (int j = 1; j < B.length; j++) {
if (A[i] == B[j]) {
dp[i][j] = dp[i - 1][j - 1] + 1;
}
if (dp[i][j] > result) {
result = dp[i][j];
}
}
}

// for (int i = 0; i < dp.length; i++) {
// System.out.println(Arrays.toString(dp[i]));
// }

return result;

}

优化解法:使用倒序遍历的方式将一维数组降维

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public static int findLengthDpQuick(int[] A, int[] B) {
int l1 = A.length;
int l2 = B.length;
if (l1 == 0 || l2 == 0) {
return 0;
}
int[] dp = new int[l2 + 1];
int max = 0;
for (int i = 0; i < l1; i++) {
for (int j = l2 - 1; j >= 0; j--) {
if (A[i] == B[j]) {
dp[j + 1] = dp[j] + 1;
if (dp[j + 1] > max) {
max = dp[j + 1];
}
} else {
dp[j + 1] = 0;
}
}
}
return max;
}

iisheng wechat
微信扫码关注 Coder阿胜