动态规划算法（Dynamic-Programming）

算法专栏

小羽

2 minute read

Those who cannot remember the past are condemned to repeat it.

那些不记得过去的人被谴责在重复过去。正是因为人能够站在过去的经验上更进一步，才能像堆积木一样，将成就越堆越高。今天我就来讲讲一个按照这种思路所设计的算法——动态规划。

I. 定义

动态规划（Dynamic-Programming, 简称DP）是一种在数学、计算机科学、管理学和经济学等等学科中使用的一种将一个复杂问题分解为相对简单的子问题，根据子问题的结果来最终解决复杂问题的一种方法。

试想一下，如果问你1+2+3+…+100 = ?这个问题时，是不是不那么容易计算出来？但是如果这个时候告诉你1+2+3+…+99 = 4950时，你就能很快的知道1+2+3+…+100 = 4950+100 = 5050.其实，这就是动态规划的思维。简而言之，动态规划算法的核心就是记住已经解决过的子问题的解，并根据这个解去解决相对复杂一点的问题，通过一层一层的求解，最终可以解决很复杂的问题。

下图是应用动态规划算法解决斐波那契数列的经典例子。假如问题是想计算出fib(6)的值，那么我们就必须先计算出fib(5)和fib(4)的值，要知道fib(4)的值，我们又需要先知道fib(3)和fib(2的值)，以此类推到最底层。因为我们知道fib(1)和fib(2)=1，那么可以因此求得fib(3)，然后求得fib(4)…最终求得fib(6)。这整个过程就是一个动态规划的过程。

avatar

II. 实现方法

实现动态规划算法，我们往往需要四个步骤：

  1. 选择状态变量
  2. 初始化
  3. 确定状态转移返程
  4. 储存结果

1. 选择状态变量

在这一步中，我们需要将问题拆分为多阶段的子问题。设置状态变量，其在前一阶段中被计算出来，并在后一阶段被使用。如下图所示，阶段1中的结果B, C被传入阶段2，并通过他们计算出结果D,C然后传入阶段3用于计算出最终结果F。这些变量便是状态变量。

avatar

2. 初始化

在这一步中，我们需要设置边界，也就是在什么情况下停止。在菲波那切数列中边界是fib(1)=1, fib(2)=1。

3. 确定转移方程

转移方程是一种方程，其描述了当前子问题的状态变量与上一层的状态变量之间的关系。在菲波那切数列中，转移方程就是fib(n) = fib(n-1) + fib(n-2)。

4.储存结果

在这一步中设置结果变量用于储存结果。

III. 经典习题

  1. Unique Paths(Leetcode 62)

A robot is located at the top-left corner of a m x n grid (marked ‘Start’ in the diagram below).

The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked ‘Finish’ in the diagram below).

How many possible unique paths are there?

avatar

这道题要我吗找出在一个mxn网格的图中，计算出从左上角到右下角一共有多少种走法。（每次只能向下和向右走一格）

首先这道题我们可以分析出，每一个方格的走法数等于其左边和上方方格的走法数之和，且在最左边和最上方的方格的走法有且只有一种。所以我们可以按照如下步骤进行解题：

  1. 创界一个二维数组来模拟网格图，其第一行和第一列的值为1。（初始化）

  2. 将每个方格的走法数作为状态变量。（确定状态变量）

  3. 将转移方程设置为每个方格的走法数（状态变量）等于其左边和上方方格的走法数之和，写成式子也就是：

   graph[i][j] = graph[i-1][j] + graph[i][j-1]
  1. 将数组的最后一行且最后一列的值设置为结果并返回。

代码

class Solution {
    public int uniquePaths(int m, int n) {
        int [][] graph = new int[m][n];
        for (int i=0; i<m;i++){
            graph[i][0] = 1;
        }
        for (int i=0; i<n; i++){
            graph[0][i] = 1;
        }
        for (int i=1; i<m;i++){
            for (int j=1;j<n;j++){
                graph[i][j] = graph[i-1][j] + graph[i][j-1];
            }
        }
        return graph[m-1][n-1];
    }
}
  1. Longest Palindromic Substring(Leetcode 5)

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

avatar

这道题是让我们找到一个String中左右对称的Substring。通过观察后我们发现，左右对称的String一共分为两种：一种是有中心的，如”bab”;一种是没有中心的，如”abba”。所以我们每次在判断一个Substring是否为中心对称的String时要判断两次。思路为遍历整个String的每一个字符,如果其中某个字符的左右两边对称，那么就储存其长度并返回true，接下来判断左右两边下一位的字符是否对称，重复此过程直到返回false为止。解题步骤如下：

  1. 设置for循环来遍历String,查看每一个字符的左右对称字符的长度。
  2. 状态变量为当前字符的左右两边相等字符的index(left和right)，如果相等就两边加一（left++, right++）继续判断是否对称，直到找到不对称的字符为止。（选择状态变量)
  3. 用while循环来实现两次动态规划，第一次left index和right index的初始值设置为和正在检查的字符的index相等（判断是否无中心对称）；第二次left index的初始值不变，right index的初始值设置为正在检查的字符的index+1（判断是否有中心对称）。（初始化）
  4. 将Substring的左右两边位置保存下来，如果有更长的就修改它，直到遍历结束为止。（保存结果）

代码

class Solution {
	public String longestPalindrome(String s) {
        if (s == null || s.length() == 0) return "";
        int start = 0;
        int end = 0;
        for (int i=0; i<s.length();i++){
            int len1 = longst(s, i, i);
            int len2 = longst(s, i, i+1);

            int len = Math.max(len1, len2);
            if (end - start < len){
                start = i - (len-1)/2;
                end = i + len/2;
            }
        }
        return s.substring(start, end+1);
    }

    private static int longst(String s, int left, int right) {
        while (left>-1 && right < s.length() && s.charAt(left)== s.charAt(right)){
            left--;
            right++;
        }
        return right-left-1;
    }
}

IV. 总结

动态规划算法是一种功能非常强大的计算机算法，其将一个复杂问题分割为若干个层层嵌套的子问题，用上一层中子问题的解来解答下一层的问题直到获得我们原本想要解的那个复杂问题的答案。在动态规划中，步骤一般如下：1.选择状态变量；2.初始化；3.确定转移方程；4.储存结果。在动态规划中，我们往往用循环或者递归来实现嵌套。

V. 参考

  1. https://blog.csdn.net/u013309870/article/details/75193592
  2. https://www.zhihu.com/question/23995189