动态规划

动态规划与贪心法的关系

基本归纳法：对于A_{i+1} ，只需要考察前一个状态A_{i} 即可完成整个推理过程，它的特点是只要状态A_{i} 确定，则计算A_{i+1} 时不需要考察更前序的状态，我们将这一模型称之为马尔科夫模型

基本归纳法

高阶归纳法：相应的，对于A_{i+1} ，需要考察前i个状态集{{x_{1}，x_{2}，x_{3}......x_{i} }}才能完成整个推理过程，往往称之为高阶马尔科夫模型

高阶归纳法

在计算机算法中，高阶马尔科夫模型的推理，叫做“动态规划”，而马尔科夫模型的推理，对应“贪心法”。


最长递增子序列LIS

    给定长度为N的数组A，计算A的最长的单调递增的子序列（不一定连续）

    如：给定数组A{5,6,7,1,2,8}，则A的LIS为{5,6,7,8}，长度为4

        长度为N的数组记为A={a_{0}, a_{1}, a_{2}...... a_{n-1}}

        记A的前i个字符构成的前缀串为A_{i}=a_{0}, a_{1}, a_{2}...... a_{n-1} ，以a_{i} 结尾的最长递增子序列记为L_{i} ，其长度为b[i]；

        假定已经计算得到了b[0,1,......,i-1]，如何计算b[i]?

            已知L_{0} L_{1} ......L_{i-1} 的前提下如何求L_{i}

                根据定义，L_{i}必须以a_{i}结尾；

                如果将a_{i}分别缀到L的后面，是否允许呢？

                    如果a_{i}\geq a_{j} ，则可以将a_{i}缀到L_{j}后面，得到比L_{j}更长的字符串

                从而：b[i]={max(b[j]+1,0<=j<i且a_{j}<=a_{i})}

                    计算b[i]：遍历在i之前的所有位置j，找出满足条件a_{j}\leq a{i}的最大的b[j]+1

                    计算得到b[0......n-1]后遍历b[i]，找出最大值即为最大递增子序列的长度。

    时间复杂度为O（n^2）


O(NlogN)的最长递增子序列算法（贪心法）

    对于数组A={1,4,5,2,8,9,7}

    将A中的数字依次遍历做压栈操作，当遇到数组中的数字比栈中某个数字大，比某个数字小的情况下，进行替换操作，最后栈中数字个数即为最大递增子序列的长度。

贪心法


    股票最大收益

        给定数组A[0......N-1]，其中A[i]表示某股票第i天的价格。如果允许最多只进行一次交易（先买一次，再卖一次），请计算合适买卖达到最大收益，返回最大收益值。

        如：[7,1,5,3,6,4]，则最大收益为6-1=5

        如：[7,6,4,3,1]，则最大收益为0

                一路下跌，则最好的方法是不进行交易。

解法


         给定数组A[0......N-1]，其中A[i]表示某股票第i天的价格。如果允许最多只进行K次交易（先买一次，再卖一次，算一次交易），请计算合适买卖达到最大收益，返回最大收益值。

            规定买卖不能嵌套，及买入后要先卖出才可再买

            如：A=[7,1,5,3,6,4]，k=3，则在1,3处买入，5,6处卖出，最大收益为7

         分析：

            dp[k,i]表示最多k次交易在第i天的最大收益。

            在第i天，有俩种选择：要么卖出股票，要不卖出股票，从而得到状态转移方程。

状态转移方程
核心代码

            进一部分析

状态转移方程转变

                

核心代码



    任务安排

        给定一台有m个存储空间的单进程机器，现有n个请求：第i个请求计算时需要占用R[i]个空间，计算完成后，存储计算结果需要占用O[i]个空间（其中O[i]<R[i]）。问如何安排这n个请求的顺序，使得所有请求都能完成。

        如：m=14，n=2，R[1,2]=[10,8]，o[1,2]=[5,6]。可以先运行第一个任务，计算时占用10个空间，计算完成后占用5个空间，剩余9个空间执行第二个任务；单如果先运行第二个任务，则计算完成后仅剩余8个空间，第一个任务的计算空间就不够了。

        算法分析：

            第K个任务的计算占用空间加上前面k-1个任务空间占用量之和，越小越好。从而：

算法分析

            得：将按照R[i]-O[i]降序排列即可


    操作最小次数

        变量x从1开始变化，规则是：要么变成x+1，要么变成2*x，问：若想将x变成整数2015，最少需要多少次变化？

        一种可行的操作变化：

        1,2,3,6,7,14,15,30,31,62,124,125,250,251,502,503,1006,1007,2014,2015

            如何思考：

        任何一个数字都可以，如：20161006

        1001100111010000111101110

二进制操作

        设dp(n)表示从1到n的最少操作数

            若n为奇数，则n的前一步只能是n-1

            若n为偶数，则n的前一步是n-1和n/2的操作步数的小者

n是如何得到

                

最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

推荐阅读更多精彩内容