如何实现动态规划？——ONE

昨天总算是看完了数据结构的图了，今天开始搞动态规划（ps：实话说，对动态规划一点概念都没有），以下均是边学动归边做的书面整理，便于梳理自己的思路，很多都是基于一些大牛的文章做的总结。
刚看到动态规划，我问了三个比较抽象的问题（也许这么问并不明智）……
一：动态规划的存在的实际意义是什么（即为了解决什么问题而存在）？
二：动态是什么？
三：什么是规划？

－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－

首先，学动态规划，我习惯性的先查找其适用的范围：
1、动态规划通常情况下应用于最优化问题，对于很多问题，答案可能不止一个，但是这些不止一个的答案中肯定存在最优的解，动归的目的就是找到这个最优的解。（ps：这也许是我的第一个问题的答案，也许还不够完善，先记着）。
2、若要使用动态规划，这个问题必须无后效应性，即后边的各种决策并不受前边的决策的影响。

其次，我就不喜欢再去看多余的概念了，因为对于我这种看视频都瞌睡的人，概念看多了会中毒的，直接看一些例题，通过在例题中自己总结动归的一些功能特性以及用法。

ONE：最大子数组和问题
一个有N个整数元素的一位数组(A[0], A[1],...,A[n-1], A[n])，这个数组当然有很多子数组，那么数组之和的最大值是什么呢？例如有数组 int A[5] = {-1, 2, 3, -4, 2}。（答案：5）再例如：
数组： {1, -2, 3, 5, -3, 2}   返回值为 8
数组： {0, -2, 3, 5, -1, 2}   返回值为 9
数组： {-9, -2, -3, -5, -6}   返回值为 -2  注意不能为空子数组

这个问题最直观的解法就是穷举法，当n小的时候，穷举法是个简单便捷的办法，但时间复杂度为O(n^2)，但是当n大的时候，显然穷举法是不明智的，所以更应该寻找一些时间复杂度低的方法，这里所要找的就是递归的方法，时间复杂度为O(n)。

再审题，明确一下要求：
    1.子数组必须是连续的。
    2.不需要返回子数组的具***置。
    3.数组中包含：正整数，零，负整数，不能为空子数组。

为了便于比较，先给出穷举法：

    int MaxSubString(int* A, int n)
    {
    　　int max = min;  //初始值为负无穷大
    　　int sum;
    　　for(int i = 0; i < n; i++)
    　　{
    　　　　sum = 0;
    　　　　for(int j = i; j < n; j++)
        　　　　{
        　　　　　　sum += A[j];
        　　　　　　if(sum > max)
        　　　　　　　　max = sum;
        　　　　}
    　　}
    　　return max;
    }   

如果想要优化这道题为递归，那就需要转变原来的穷举的思维，可以先考虑一个元素，以及最大的一段数组（假设知道这段数组为A[i],...,A[j]），考虑和第一个元素A[0]的关系，有以下三种情况：
1. 当0 = i = j 时，元素A[0]本身构成和最大的一段;
2. 当0 = i < j 时，和最大的一段以A[0]开始;
3. 当0 < i 时， 元素A[0]和最大的一段没有关系。

**这样分析，就可以将一个大的问题（N个元素数组）转化为一个较小的问题（N-1个元素数组）。假设我们已经知道第二个数到最后一个数中子数组最大的和为All[1]，并且已经知道(A[1],...,A[n-1])中包含A[1]的和最大的一段数组为Start[1]。那么分析上述三种情况就不难看出 (A[0], ..., A[n])中问题的解All[0] = max{ A[0], A[0] + start, All }。**  通过这样的分析就可以看出这道题无后效应性，那么就用动归来实现它。

    int MaxSubString(int* A, int n)
    {
        int All[n],Start[n],i;
        Start[n - 1] = A[n - 1];
        All[n - 1] = A[n - 1];                   
        for(i = n - 2; i >= 0; i--)        //根据题意，从后向前遍历，反之亦可。
        {
            Start[i] = max(A[i], A[i] + Start[i + 1]); 
            //Start[i]表示第一个元素为A[i]的和最大的子数组和，Start[i + 1]也可以理解为把A[i]后边的包括A[i + 1]的和最大的子数组整合为一个整数Start[i + 1]，如果Start[i + 1] > 0时，则加上后边的子数组，否则不加
            All[i] = max(Start[i], All[i + 1]);  //重难点，需要慢慢理解
        }
        return All[0];                       //All[0] 中存放结果
    }

个人感觉，这个方法中有点递推的影子，也许动归本身就和递推有些关系。这个动归不止是时间复杂度低，代码也很简洁（当然，在很多情况下，时间复杂度低的代码，代码会更加复杂，更加长）。学到这里，我想我可以初步回答自己的第二个问题：动态是什么？
所谓动态，需要与静态（这里的静态和编程中的狭义上的静态不是一回事）放在一起讲。
个人理解，静态的算法，如上述的穷举法，绝大多数程序员都可以轻松知道执行过第一步的数据接着怎么执行第二步数据，第二部数据该是什么，这都是很轻松就可以知道的，因为这很清晰，执行过j=1,就该执行j=2，至于max就取历史数据中sum最大的那个，并且sum可以很直观的通过i和j的值来推断出他是怎么得到的。（穷举法中只有max的大小需要用到sum的历史数据，并且纯粹只是为了取到最大的max值，我称这种算法是相对于动态规划的静态算法）
然而在动归中，我们无法轻松的根据知道i的值来判断最大值是怎么得到的，因为他与i的值没有直接的关联，是每一步都建立在上一步求出来的结果上，再进一步扩大范围并融入上一部的结果而最终得到了All[0]。就如同人们盖房子，先打地基，再在地基的基础上盖墙与瓦。每一步都需要完全建立在上一步的完成，并且我们并不会因为地基用的材料（假如都足够牢固）不同，而导致我们后边用的墙和瓦的材料不同，导致的只是最后整体房子的好坏，当然动归是为了以最短的时间建最好的房子。
这时，你也许会说，我所谓的静态算法之一——“穷举法”，也是需要建立在上前边的步骤来取到最大的max。那我会告诉你，你说的不完全对，注意我的言辞，动归是完全建立在前边的运行基础上，然而穷举法我们大可以把每个num都存在一个数组中，最后求出数组中的最大值，当然这么做的人简直就是傻透了。可是道理就是这样的。不傻的人只是把比较的过程融入了穷举的过程。

综上所述，把穷举法再衍生出来一种先将sum存储，再比较取最大的max的值的方法，我们暂且称其为穷举衍生法，那么我们现在来整体的通俗的梳理一遍三者的区别（我们还用盖房子的事讲）。
我们现在想盖一个最好的房子（即盖房子问题的最优解），最好的是什么样子呢？（不求怎么盖，只求最好的程度有多好）
一、穷举法：穷举法就相当于我们先盖好第一个，再盖第二个，然后比较，留下最好的一个，另外一个想怎么处理都行，反正我们是不需要它了，他已经没有存在价值了，我们姑且以为把它拆掉了，然后我们再盖第三个房子，再比较，再拆掉相对差的房子，以此不断重复，最终留下了最好的房子。
二：穷举衍生法：穷举衍生法就是先将所有的房子都盖好，最后统一比较哪个最好，留下最好的，其他的都拆掉就好了。
三：动态规划：动态规划比较难理解，准确点形容，它就像是盖楼房，最后我们只留下最高的一层，即最好的一层。我们都知道，房子分为两部分，墙（为了描述更佳形象，这里不考虑地基）和顶。动态规划就是我们每次都盖一层，但是不封顶，接着去规划第二层，规划好后，这时我们面临两种情况，（一）、规划好的第二层比第一层好，那么我们就将第一层拆去，只留下第二层，将其重置为第一层，（二）、第一层比规划好的第二层更好，那么我们就放弃这个规划好的，重新再一次规划，（即实现了动态规划，我们的每一次规划都是不受前面影响的，但是我们是否保留这次规划是受前边影响的，因为是否保留会影响到最终的房子的好坏）。以此循环，每次都保留最好的一层（墙），将不好的拆掉或者不建，最后我们再对房子进行封顶，即得到All[0]。也就是保留下来了最好的房子。
这里需要注意，我们这里的影响并不是后效应性，换言之，是和后效应性有本质区别的，所谓后效应性是前面的决策会影响到后边的决策，但是我们这里影响的并不是后边的决策，而是最终的结果，这就使动态规划有了可行性。

总而言之，穷举法和穷举衍生法换汤不换药，都是一个思路，而动态规划的思路和这两者完全不同，前两者都是把所有的可能的房子都盖好，最后只留下最好的，他们其实就是在做不同的墙和不同的顶随机搭配的过程，n个墙（外循环），n个顶（内循环），最后时间复杂度为O(n^2)；而动态规划则是每次只考虑墙（n个墙），而对于每个墙都有固定的最好的顶搭配，所以我们只在建墙的同时，记录每个墙恰好的顶（其实All数组就是记录顶的，只不过没有直接纪录顶的位置，而是记录下来对应下标的墙盖好的最好的房子的好坏，毕竟我们只求最好的房子有多好），最后留下最好的墙（好吧，我承认，其实这里并没有记录最好的墙的位置，而是直接纪录的是房子的好坏程度），并进行封顶，得到最好的房子好的程度有多少。

大致就是这个区别，自己总结的并不够好，但是这是我自己对动态规划的深刻理解，并比较了他和非动态规划的区别。题没有多难，难的是第一次接触动态规划，还不知道动态规划是什么东西，想要深入理解，是个很艰难的过程！！！

这样就只剩下第三个问题，这时我都笑了，这算什么问题，我竟然还放在了第三个位置，太愚蠢了，但是不能否认的是，在我接触新鲜的事物时，无法避免的总要问些愚蠢的问题，没有这些愚蠢的问题，我又怎么能激发自己去深入学习自己接触的新鲜事物呢？
想要不问愚蠢的问题，那就是不问问题，但是这样，你表面显得自己很机智，而实际上，你无法永远掩盖住自己的愚蠢……
在这里，我真的要说一句：向愚蠢的问题致敬！！！
善始善终，既然问了，就要回答出来：
A：什么是规划？
B：规划即决策。
C：什么是决策？
B：那我只能呵呵了！！！
当然，我开始是A，后来是B，但是绝不会是C，因为，凡事要有度，物极必反。过度愚蠢的问题还是不要问的好，因为那只能说明我们真的智商余额不足，不适合学编程，更不适合走算法！（偷偷告诉你，如果你有C的问题，那么你就算不问出来，我也要建议你去另谋他路吧！）

咳咳，博客差不多长就够了，再长就说不过去了。但是关于动态规划的问题，我才只说到了入门理解层次，还没有真正的上硬菜，所以……待续喽！！！～