动静布局就是 1 +1

1 – 什么是动静布局？

    首先援用一下 Wikipedia 的词条，咱们来认识一下动静布局。

Dynamic programming is both a mathematical optimization method and a computer programming method. The method was developed by Richard Bellman in the 1950s and has found applications in numerous fields, from aerospace engineering to economics.

In both contexts it refers to simplifying a complicated problem by breaking it down into simpler sub-problems in a recursive manner. While some decision problems cannot be taken apart this way, decisions that span several points in time do often break apart recursively. Likewise, in computer science, if a problem can be solved optimally by breaking it into sub-problems and then recursively finding the optimal solutions to the sub-problems, then it is said to have optimal substructure.

If sub-problems can be nested recursively inside larger problems, so that dynamic programming methods are applicable, then there is a relation between the value of the larger problem and the values of the sub-problems.[1] In the optimization literature this relationship is called the Bellman equation.

    其中最重要的一句话是 ”it refers to simplifying a complicated problem by breaking it down into simpler sub-problems in a recursive manner.”。意思是“动静布局应用递归的形式将一个简单的问题合成为更简略的子问题解决问题。”。乍一听，感觉动静布局比拟艰涩，像是个深奥的数学问题。其实，咱们每天都在接触动静布局。给大家 举个栗子 ，咱们在计算1 + 1 的时候，脑子条件反射般的算出答案，没错，等于 2。然而当咱们算 1 + 1 + 1 + 1 的时候，大家就会算得1 + 1 = 2，而后2 + 1 = 3，最初3 + 1 = 4，这也正是是乘法的实质。动静布局的原理也不过如此，将简单的问题合成为简略的子问题。

    咱们通过这个例子，不难发现其中几个须要留神的点。第一，做这个 ”1+1″ 难题的时候，最重要的是什么？是咱们晓得后一项等于前一项加一，所以咱们发现，动静布局不仅仅是将大问题化简为小问题，在这其中有一个必要条件，那就是大问题和子问题之间的关系 ，咱们把它叫做“状态转移“。在此例中，状态转移的法则非常明显。a[n] = a[n-1] + 1。 咱们把这种状态转移的公式化形容叫做状态转移方程 。第二个须要留神的点也很容易找到，咱们总是用前一项推导后一项的值，那么最后面的一项用什么来推导呢？答案是无奈推到。 那么咱们指定一个初始值，方能应用状态转移方程推导简单问题，咱们管这个初始值叫做初始状态。这有点相似于虹吸原理。可能大家都有过这样的经验，水缸里有一缸水，咱们要将其排出，那最简略的方法是什么呢？让其利用虹吸原理主动流进去，那最外围的步骤就是，咱们首先须要在管子的一头用嘴巴吸出第一口水，给其一个初始动能。这就是初始状态的意义。

2 – 斐波那契数列和动静布局的渊源

    家喻户晓，斐波那契的定义是a[n] = a[n-1] + a[n-2]，咱们能很显著的发现其中的一项是由前两项的和组成的。那么这不久刚好匹配了动静布局的定义吗？咱们来尝试应用动静布局的思维求解斐波那契数列，感受一下动静布局为什么高效。

public static int fib(int n) {
        // 边界查看
        if (n <= 0) throw new IllegalArgumentException("n 必须大于 0");
        if (n <= 2) return n;

        // 确定状态 (开一个数组，明确数组的索引和值之间的对应关系  例如: 第 i 个元素示意 fib(i))
        int[] dp = new int[n];

        // 初始状态
        dp[0] = 1;
        dp[1] = 1;

        // 状态转移
        for (int i = 2; i < n; i++) {dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n - 1];
    }

    在咱们实际中发现，还有两个步骤是必不可少的，边界检查和确定状态，确定不了状态无奈用程序示意出状态转移方程，没有边界查看，咱们就无奈保障程序正确运行。所以这四个步骤，就是动静布局的全副。用班主任的口气来讲，动静布局是万变不离其宗！

3 – 实际出真知

    咱们通过几个例子，来坚固一下动静布局的解题思路。

70. 爬楼梯

    印象十分粗浅，这是美团已经的一道口试题，属于非常简单的入门题了。跟斐波那契数列一个接替思路，惟一要留神的是初始状态的界定。

    public int climbStairs(int n) {
        // 边界查看
        if(n <= 0) return 0;
        if(n > 0 && n <= 2) return n;

        // 确定状态
        int[] dp = new int[n];

        // 初始状态
        dp[0] = 1;
        dp[1] = 2; // FBI WARNING !!!

        for(int i = 2; i < n; i++){dp[i] = dp[i-1] + dp[i-2];
        }

        return dp[n - 1];
    }

300. 最长回升子序列

    这道题的难点在于如何找到状态转移方程，这也是绝大多数动静布局题目的难点，咱们对此进行剖析。首先要确定状态，咱们的 dp 数组到底示意什么？一般来讲，题目的后果是什么，dp 数组的值就是什么，而后再去找索引对应的含意，这是个浏览了解题……。”dp[i]示意以 nums[i]结尾的 LIS 的长度“，这就是咱们这道题中状态的含意，咱们待会以此推出状态转移方程。

public int longestCommonSubsequence(String text1, String text2) {int m = text1.length(), n = text2.length();
        // dp[i][j] 示意：字符串 str1[0:i] 和字符串 str2[0:j] 的最大公共子序列
        int[][] dp = new int[m+1][n+1];
        // 进行状态转移
        for(int i = 1; i <= m; i++){for(int j = 1; j <= n; j++){if(text1.charAt(i-1) == text2.charAt(j-1)){ // 若两个字符相等，必然能够形成子问题的最优解
                    // 这个字符存在于 lcs 之中
                    dp[i][j] = dp[i-1][j-1] + 1; 
                }else{dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]);  
                }
            }
        }
        return dp[m][n];
    }

动静布局的题目还有很多，例如求最值，博弈等，最大的难点就是找状态转移方程，只有多刷题才可能齐全把握，学得基本原理之后，接下来就是分割啦！