0%

动态规划算法

发表于 更新于 Valine：

动态规划的适用场景

动态规划常常适用于有重叠子问题和最优子结构性质的问题，动态规划方法所耗时间往往远少于朴素解法。

动态规划的基本思想

动态规划背后的基本思想非常简单。大致上，若要解一个给定问题，我们需要解其不同部分（即子问题），再合并子问题的解以得出原问题的解。
通常许多子问题非常相似，为此动态规划法试图仅仅解决每个子问题一次，从而减少计算量：一旦某个给定子问题的解已经算出，则将其记忆化存储，以便下次需要同一个子问题解之时直接查表。这种做法在重复子问题的数目关于输入的规模呈指数增长时特别有用。

重叠子问题

动态规划在查找有很多重叠子问题的情况的最优解时有效。它将问题重新组合成子问题。为了避免多次解决这些子问题，它们的结果都逐渐被计算并被保存，从简单的问题直到整个问题都被解决。因此，动态规划保存递归时的结果，因而不会在解决同样的问题时花费时间。

最优子结构

动态规划只能应用于有最优子结构的问题。最优子结构的意思是局部最优解能决定全局最优解（对有些问题这个要求并不能完全满足，故有时需要引入一定的近似）。简单地说，问题能够分解成子问题来解决。

动态规划的三要素

  • 最优子结构性质。如果问题的最优解所包含的子问题的解也是最优的，我们就称该问题具有最优子结构性质（即满足最优化原理）。最优子结构性质为动态规划算法解决问题提供了重要线索。
  • 无后效性。即子问题的解一旦确定，就不再改变，不受在这之后、包含它的更大的问题的求解决策影响。
  • 子问题重叠性质。子问题重叠性质是指在用递归算法自顶向下对问题进行求解时，每次产生的子问题并不总是新问题，有些子问题会被重复计算多次。动态规划算法正是利用了这种子问题的重叠性质，对每一个子问题只计算一次，然后将其计算结果保存在一个表格中，当再次需要计算已经计算过的子问题时，只是在表格中简单地查看一下结果，从而获得较高的效率。

动态规划算法的设计步骤：

  1. 刻画最优解的结构特征（寻找最优子结构）
  2. 递归地定义最优解的值（确定状态转移方程）
  3. 计算最优解的值（有两种方法：带备忘录自顶向下法、自底向上法）
  4. 利用计算出的信息构造一个最优解（通常是将具体的最优解输出）

一般的解法

把动态规划的解法分为自顶向下和自底向上两种方式。
自顶向下的方式其实就是使用递归来求解子问题，最终解只需要调用递归式，子问题逐步往下层递归的求解。我们可以使用缓存把每次求解出来的子问题缓存起来，下次调用的时候就不必再递归计算了。
自底向上是另一种求解动态规划问题的方法，它不使用递归式，而是直接使用循环来计算所有可能的结果，往上层逐渐累加子问题的解。

LeetCode题

1. House Robber题目，转化过来的意思是，一个数组nums[]，求最大的不存在相邻元素的子数组的和。

用动态规划的递归解法,自顶向下。时间复杂度O(nlogn)，空间复杂度O(1)

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
//Time Limit Exceeded
public int robRecursiveDP(int[] nums, int length) {
    if (length == 0) {
        return 0;
    }

    if (length == 1) {
        return nums[0];
    }

    if (length == 2) {
        return Math.max(nums[0], nums[1]);
    }

    int rob1 = robRecursiveDP(nums, length - 1);
    int rob2 = robRecursiveDP(nums, length - 2);

    if (rob1 == rob2) {
        return rob1 + nums[length - 1];
    } else if (rob1 > rob2) {
        return Math.max(rob2 + nums[length - 1], rob1);
    } else {
        System.out.println("data error");
        return 0;
    }

动态规划的状态转移方程：
dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1]);
dp[i][1] = num[i - 1] + dp[i - 1][0];

用动态规划的自底向上解法, 时间复杂度O(n)，空间复杂度O(n)

1
2
3
4
5
6
7
8
9
// 300ms
public int robDP(int[] num) {
    // dp[i][1] means we rob the current house and dp[i][0] means we don't
    int[][] dp = new int[num.length + 1][2];
    for (int i = 1; i <= num.length; i++) {
        dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1]);
        dp[i][1] = num[i - 1] + dp[i - 1][0];
    }
    return Math.max(dp[num.length][0], dp[num.length][1]);

用带备忘录的自底向上动态规划的解法, 时间复杂度O(n)，空间复杂度O(1)

1
2
3
4
5
6
7
8
9
10
11
// 250ms
public int rob(int[] num) {
	int prevNo = 0;
    int prevYes = 0;
    for (int n : num) {
        int temp = prevNo;
        prevNo = Math.max(prevNo, prevYes);
        prevYes = n + temp;
    }
    return Math.max(prevNo, prevYes);
}

2. House Robber2题目，转化过来的意思是，一个数组nums[], 首尾看成相邻，求最大的不存在相邻元素的子数组的和。

Actually, extending from the logic that if house i is not robbed, then you are free to choose whether to rob house i + 1, you can break the circle by assuming a house is not robbed.
For example, 1 -> 2 -> 3 -> 1 becomes 2 -> 3 if 1 is not robbed.
Since every house is either robbed or not robbed and at least half of the houses are not robbed, the solution is simply the larger of two cases with consecutive houses, i.e. house i not robbed, break the circle, solve it, or house i + 1 not robbed. Hence, the following solution. I chose i = n and i + 1 = 0 for simpler coding. But, you can choose whichever two consecutive ones.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int robCycle(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }
        if (nums.length == 1) {
            return nums[0];
        }

        if (nums.length == 2) {
            return Math.max(nums[0], nums[1]);
        }

        return Math.max(rob(Arrays.copyOfRange(nums, 0, nums.length - 1)),
                rob(Arrays.copyOfRange(nums, 1, nums.length)));
}

3. Maximum Subarray题目，求最大连续子数组和。

不用动态规划的解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public int maxSubArray(int[] nums) {
    int sumMax = nums[0], sum = 0;
    for (int num : nums) {
        sum += num;
        if (sum < num) {
            sum = num;
        }
        if (sum >= sumMax) {
            sumMax = sum;
        }
    }

    return sumMax;
}

动态规划的状态转移方程：dp[i] = Math.max(dp[i - 1] + nums[i - 1], nums[i - 1]);

用动态规划的自底向上解法, 时间复杂度O(n)，空间复杂度O(n)

1
2
3
4
5
6
7
8
9
10
public int maxSubArrayDP(int[] nums) {
    int sumMax = nums[0];
    int[] dp = new int[nums.length + 1];
    for (int i = 1; i <= nums.length; i++) {
        dp[i] = Math.max(dp[i - 1] + nums[i - 1], nums[i - 1]);
        sumMax = Math.max(sumMax, dp[i]);
    }

    return sumMax;
}

用带备忘录的自底向上动态规划的解法, 时间复杂度O(n)，空间复杂度O(1)

1
2
3
4
5
6
7
8
9
public int maxSubArrayDPWithMem(int[] nums) {
    int sumMax = nums[0], sumPre = 0;
    for (int i = 1; i <= nums.length; i++) {
        sumPre = Math.max(sumPre + nums[i - 1], nums[i - 1]);
        sumMax = Math.max(sumMax, sumPre);
    }

    return sumMax;
}

4. Interleaving String题目，Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2.
For example,
Given:
s1 = “aabcc”,
s2 = “dbbca”,
When s3 = “aadbbcbcac”, return true.
When s3 = “aadbbbaccc”, return false.

动态规划的递归调用解法，时间复杂度不符合要求。

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
public boolean isInterleaveRecursiveDP(String s1, String s2, String s3) {
    if (s3.length() != s1.length() + s2.length()) {
        return false;
    }

    if (s1.length() == 0 && s2.length() == 0 && s3.length() == 0) {
        return true;
    } else if (s3.length() == 0) {
        return false;
    }

    String newS3 = s3.substring(0, s3.length() - 1);
    String newS1 = s1.length() > 0 ? s1.substring(0, s1.length() - 1) : "";
    String newS2 = s2.length() > 0 ? s2.substring(0, s2.length() - 1) : "";

    boolean equalS1 = s1.length() > 0 && (s1.charAt(s1.length() - 1) == s3.charAt(s3.length() -
            1));
    boolean equalS2 = s2.length() > 0 && s2.charAt(s2.length() - 1) == s3.charAt(s3.length() -
            1);

    if (equalS1 && !equalS2) {
        return isInterleaveRecursiveDP(newS1, s2, newS3);
    } else if (!equalS1 && equalS2) {
        return isInterleaveRecursiveDP(s1, newS2, newS3);
    } else if (equalS1 && equalS2) {
        return isInterleaveRecursiveDP(newS1, s2, newS3) || isInterleaveRecursiveDP(s1, newS2, newS3);
    } else {
        return false;
    }
}

动态规划带备忘录自底向上的解法，难点就在于如何将解法1的递归公式转化为动态转移方程，下述代码构造的二维数组很好地诠释了这一点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public boolean isInterleaveDP(String s1, String s2, String s3) {
    if (s3.length() != s1.length() + s2.length())
        return false;

    boolean[][] table = new boolean[s1.length() + 1][s2.length() + 1];

    for (int i = 0; i < s1.length() + 1; i++)
        for (int j = 0; j < s2.length() + 1; j++) {
            if (i == 0 && j == 0)
                table[i][j] = true;
            else if (i == 0)
                table[i][j] = (table[i][j - 1] && s2.charAt(j - 1) == s3.charAt(i + j - 1));
            else if (j == 0)
                table[i][j] = (table[i - 1][j] && s1.charAt(i - 1) == s3.charAt(i + j - 1));
            else
                table[i][j] = (table[i - 1][j] && s1.charAt(i - 1) == s3.charAt(i + j - 1) ||
                        (table[i][j - 1] && s2.charAt(j - 1) == s3.charAt(i + j - 1)));
        }

    return table[s1.length()][s2.length()];
}
觉得不错，就打赏一下吧