前几天做leetcode的算法题很多题都提到了动态规划算法，那么什么是动态规划算法，它是什么样的思想，适用于什么场景，就是我们今天的主题。

首先我们提出所有与动态规划有关的算法文章中都会提出的观点：　将一个问题拆成几个子问题，分别求解这些子问题，即可推断出大问题的解。

什么都不了解的话看到这句话是懵逼的，我们也先略过，等看完整篇文章再回过头来看一看这个观点。

下面正式开始。

首先我们来看这个译名，动态规划算法。这里的动态指代的是递推的思想，算法在实现的过程中是动态延伸的，而不是提前控制的。规划指的是需要我们给出动态延伸的方法和方向。

这两个就是算法的问题点。

我们来看个例子（例子来源：https://www.zhihu.com/question/23995189特别推荐这篇回答，非常的简单且详细）。

　　假设您是个土豪，身上带了足够的1、5、10、20、50、100元面值的钞票。现在您的目标是凑出某个金额w，需要用到尽量少的钞票。
　　依据生活经验，我们显然可以采取这样的策略：能用100的就尽量用100的，否则尽量用50的……依次类推。在这种策略下，666=6×100+1×50+1×10+1×5+1×1，共使用了10张钞票。
　　这种策略称为“贪心”：假设我们面对的局面是“需要凑出w”，贪心策略会尽快让w变得更小。能让w少100就尽量让它少100，这样我们接下来面对的局面就是凑出w-100。长期的生活经验表明，贪心策略是正确的。
　　但是，如果我们换一组钞票的面值，贪心策略就也许不成立了。如果一个奇葩国家的钞票面额分别是1、5、11，那么我们在凑出15的时候，贪心策略会出错：
　　15=1×11+4×1 （贪心策略使用了5张钞票）
　　15=3×5 （正确的策略，只用3张钞票）
　　为什么会这样呢？贪心策略错在了哪里？
　　鼠目寸光。
　　刚刚已经说过，贪心策略的纲领是：“尽量使接下来面对的w更小”。这样，贪心策略在w=15的局面时，会优先使用11来把w降到4；但是在这个问题中，凑出4的代价是很高的，必须使用4×1。如果使用了5，w会降为10，虽然没有4那么小，但是凑出10只需要两张5元。
　　在这里我们发现，贪心是一种只考虑眼前情况的策略。
　　那么，现在我们怎样才能避免鼠目寸光呢？
　　如果直接暴力枚举凑出w的方案，明显复杂度过高。太多种方法可以凑出w了，枚举它们的时间是不可承受的。我们现在来尝试找一下性质。

　　重新分析刚刚的例子。w=15时，我们如果取11，接下来就面对w=4的情况；如果取5，则接下来面对w=10的情况。我们发现这些问题都有相同的形式：“给定w，凑出w所用的最少钞票是多少张？”接下来，我们用f(n)来表示“凑出n所需的最少钞票数量”。
　　那么，如果我们取了11，最后的代价（用掉的钞票总数）是多少呢？
　　明显  ，它的意义是：利用11来凑出15，付出的代价等于f(4)加上自己这一张钞票。现在我们暂时不管f(4)怎么求出来。
　　依次类推，马上可以知道：如果我们用5来凑出15，cost就是  。
　　那么，现在w=15的时候，我们该取那种钞票呢？当然是各种方案中，cost值最低的那一个！
　　- 取11： cost=f[4]+1=4+1=5
　　- 取5：  cost=f[10]+1=2+1=3
　　- 取1：  cost=f[14]+1=4+1=5
　　显而易见，cost值最低的是取5的方案。我们通过上面三个式子，做出了正确的决策！

我们来看看这其中规划的展现部分，规划展现在情况分类上，我们只有三种钱币，所以会要求实现f[n]中的n要大于某一个规定值才是可取的，要10元时候我们不可以取出11元，所以在这部分要进行单独判断。

再说动态部分，显然，f[4],f[10],f[14]是我们需要单独去计算的，那么如何计算呢，就需要他们动态的去递推下一步如何计算。

来看看这个式子：f(n)=min{f(n-1),f(n-5),f(n-11)}+1

显然f(n)直接由后三个值决定，我们只要算出这三个值即可，而这三个值又由同样式的更小值决定，只要得出更小值，甚至最小值，我们就可以推导出f(n)。

我们以O（n）的复杂度解决了这个问题。现在回过头来，我们看看它的原理：
　　- f（n）只与f（n-1）f（n-5）f（n-11）的值相关。
　　-  我们只关心  的值，不关心是怎么凑出w的。　
    　这两个事实，保证了我们做法的正确性。它比起贪心策略，会分别算出取1、5、11的代价，从而做出一个正确决策，这样就避免掉了“鼠目寸光”！
    　它与暴力的区别在哪里？我们的暴力枚举了“使用的硬币”，然而这属于冗余信息。我们要的是答案，根本不关心这个答案是怎么凑出来的。譬如，要求出f(15)，只需要知道f(14),f(10),f(4)的值。其他信息并不需要。我们舍弃了冗余信息。我们只记录了对解决问题有帮助的信息——f(n).　　我们能这样干，取决于问题的性质：求出f(n)，只需要知道几个更小的f(c)。我们将求解f(c)称作求解f(n)的“子问题”。

实际上是一种冗余信息的反向筛查算法，是暴力枚举的简化。

来看看使用DP算法的要求。

【无后效性】　
　一旦f(n)确定，“我们如何凑出f(n)”就再也用不着了。　　要求出f(15)，只需要知道f(14),f(10),f(4)的值，而f(14),f(10),f(4)是如何算出来的，对之后的问题没有影响。　　
“未来与过去无关”，这就是无后效性。　　
（严格定义：如果给定某一阶段的状态，则在这一阶段以后过程的发展不受这阶段以前各段状态的影响。）
【最优子结构】
　　回顾我们对f(n)的定义：我们记“凑出n所需的最少钞票数量”为f(n).　　f(n)的定义就已经蕴含了“最优”。利用w=14,10,4的最优解，我们即可算出w=15的最优解。
　　大问题的最优解可以由小问题的最优解推出，这个性质叫做“最优子结构性质”。　　引入这两个概念之后，我们如何判断一个问题能否使用DP解决呢？　
　能将大问题拆成几个小问题，且满足无后效性、最优子结构性质。

这也同时揭示了我一开始写的那句话，大问题由小问题累积而成，是必要的。

【DP三连】　　
设计DP算法，往往可以遵循DP三连：　　
我是谁？  ——设计状态，表示局面　　
我从哪里来？　　我要到哪里去？  ——设计转移　　
设计状态是DP的基础。接下来的设计转移，有两种方式：一种是考虑我从哪里来（本文之前提到的两个例子，都是在考虑“我从哪里来”）；另一种是考虑我到哪里去，这常见于求出f(x)之后，更新能从x走到的一些解。这种DP也是不少的，我们以后会遇到。　　
总而言之，“我从哪里来”和“我要到哪里去”只需要考虑清楚其中一个，就能设计出状态转移方程，从而写代码求解问题。前者又称pull型的转移，后者又称push型的转移。

实际的例子我用前两天的几道动态规划的算法题来举例。

一道一道来：

1.Delete Operation for Two Strings

java：

class Solution {
    public int minDistance(String s1, String s2) {
        char[] cs1 = s1.toCharArray(), cs2 = s2.toCharArray();
        int n = s1.length(), m = s2.length();
        int[][] f = new int[n + 1][m + 1];
        for (int i = 0; i <= n; i++) f[i][0] = i;
        for (int j = 0; j <= m; j++) f[0][j] = j;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                f[i][j] = Math.min(f[i - 1][j] + 1, f[i][j - 1] + 1);
                if (cs1[i - 1] == cs2[j - 1]) f[i][j] = Math.min(f[i][j], f[i - 1][j - 1]);
            }
        }
        return f[n][m];
    }
}

public class towString {
    String s1 = "ba";
    String s2 = "ac";
    int x =minDistance(s1,s2);

    public int  minDistance(String s1,String s2){
        char[] cs1 = s1.toCharArray();
        char[] cs2 = s2.toCharArray();
        //拆分为字符数组
        int n = s1.length();
        int m = s2.length();
        int[][] f = new int[n+1][m+1];//+1其实是为了空出“哨兵”,也就是00位，不加在后面剪了也一样
        for(int i =0;i<=n;i++) {
            f[i][0] = i ;
            System.out.println("i="+i);
        }

        for(int j =0;j<=m;j++) {
            f[0][j] = j ;
            System.out.println("j="+j);
        }//虽然我们都知道里面是什么，但是还是输出一下;

        for(int j =1;j<=m;j++){//注意这里从1开始
            for(int i=1;i<=n;i++){
                System.out.println("f[i-1][j] = "+f[i-1][j]);
                System.out.println("f[i][j-1] = "+f[i][j-1]);
                //输出一下

                f[i][j] = Math.min(f[i-1][j]+1,f[i][j-1]+1);
                System.out.println("f[i][j]="+f[i][j]);
                System.out.println("*****************");

                System.out.println("cs1[i-1]="+cs1[i-1]);
                System.out.println("cs2[j-1]="+cs2[j-1]);
                if(cs1[i-1] == cs2[j-1]){
                    System.out.println("相同");
                    f[i][j] = Math.min(f[i][j],f[i-1][j-1]);
                }
                System.out.println("f[i][j]="+f[i][j]);
            }
        }
        for(int i =0;i<=n;i++){
            for (int j =0 ;j<=m;j++){
                System.out.print(f[i][j]+"  ");
            }
            System.out.println("\n");
        }
        return f[n][m];
    }
}

这里的特殊点在于需要每一步都比较，也就是[i-1][j]与[j][i-1]，而不是[i][j]；

5就不说了，是标准的最长公共子序列问题，上一道问题的缩减版，注意的是由于要求最长长度，所以用的是max。

6.Regular Expression Matching

class Solution {
    public boolean isMatch(String s, String p) {
        int m = s.length();
        int n = p.length();

        boolean[][] f = new boolean[m + 1][n + 1];
        f[0][0] = true;
        
        for (int i = 0; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (p.charAt(j - 1) == '*') {
                    f[i][j] = f[i][j - 2];
                    if (matches(s, p, i, j - 1)) {
                        f[i][j] = f[i][j] || f[i - 1][j];
                    }
                } else {
                    if (matches(s, p, i, j)) {
                        f[i][j] = f[i - 1][j - 1];
                    }
                }
            }
        }
        return f[m][n];
    }

    public boolean matches(String s, String p, int i, int j) {
        if (i == 0) {
            return false;
        }
        if (p.charAt(j - 1) == '.') {
            return true;
        }
        return s.charAt(i - 1) == p.charAt(j - 1);
    }
}

这道题考虑到一个问题点就是在特殊情况下的判断问题，我们抛开matches函数再看这道题的话，流程是一样的，创建，问题拆分，返回。

一般难点在于问题拆分部分，想要节省空间可以从创建部分下手，部分情况下可以降低数组维度。

以上。

（其实比较难的题，我自己拆分问题很多情况下也拆不好hhhhh，看看题解吧。）