[关闭]
@zhuanxu 2018-02-07T02:54:57.000000Z 字数 1006 阅读 507

动态规划

algorithm


认知

认识事物的方法:概念、判断、推理,而推理又分为归纳、演绎。

数学归纳法

最简单和常见的数学归纳法是证明当n等于任意一个自然数时某命题成立。证明分下面两步:

  1. 证明当n = 1 时命题成立。
  2. 证明如果在n = m时命题成立,那么可以推导出在n = m+1 时命题也成立。(m代表任意自然数)


整个过程就像多米诺骨牌,只要前一个倒下,那么与其相邻的下一张骨牌也会倒。

第二数学归纳法

第二数学归纳法原理是设有一个与正整数 n 有关的命题,如果:
(1)当 n=1 时,命题成立;
(2)假设当 n≤k(k∈N)时,命题成立,由此可推得当 n=k+1 时,命题也成立。
那么根据①②可得,命题对于一切正整数 n 来说都成立。

上面两个的区别就在于对信息的使用上:

套路:3+1

  1. 计算过程可视化
    当面对问题无头绪的时候,我们尝试着将自己的思路画出来,能有助于我们理清思路。
  2. 子问题拆解
    计算机思维中一个很重要的就是通过模块化,将复杂问题拆解为一系列简单的问题。
  3. 打破假设
    这是寻找到新解法的关键,我们需要突破假设,才能找到另一片天地。

还有最后一个原则就是类比,我们需要不断去总结现有的知识,然后将遇到的新东西都建立到我们现有的知识树上。

下面是一些动态规划的具体题目。

股票最大收益

问题描述:
给定数组A[1,2...N],其中A[i]表示某股票第i天的价格,我们同时最多持有一股,如果只能进行一次买卖,如何利润最大化? 例如股票的变化是:1, 4, 9, 2, 7, 3
最好的方案是:1买9卖,获利8,如果一路下跌,则最好的方法是不进行交易。

我们第一步先讲整个过程可视化。

通过画图我们就知道了过程了,下面看代码:

下面我们加大难度,能够进行k次交易,规定买卖不能嵌套,即:买入后,要先卖出才可再买。
如:A=[7,1,5,3,6,4],K=3,则在1,3处买入, 5,6处卖出,最大收益为7。

我们还是先来画图:

从图中我们就有了下面的代码:

总结

本文复习了下动态规划,并且举了个例子来说如何解决动态规划问题,记住套路:3+1。

你的鼓励是我继续写下去的动力,期待我们共同进步。
这个时代,每个人都是超级个体!关注我,一起成长!

添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注