动态规划思想

点击打开在线编译器,边学边练

1.简介

动态规划(dynamic programming)是运筹学的一个分支,是求解决策过程(decision process)最优化的数学方法。20世纪50年代初美国数学家R.E.Bellman等人在研究多阶段决策过程(multistep decision process)的优化问题时,提出了著名的最优化原理(principle of optimality),把多阶段过程转化为一系列单阶段问题,利用各阶段之间的关系,逐个求解,创立了解决这类过程优化问题的新方法——动态规划。

动态规划也是学习算法的同学最为头疼的一个重要算法,其类型宽泛让人无从下手,又极其的烧脑很难理解,事实上,动态规划是算法学习者的一个重要的门槛,也是一个瓶颈,掌握方法很重要,本节虽然不提供任何的具体代码,但希望简介以及介绍曲线的方式让读者能够更好的掌握。

2.思想

动态规划的基本思想是:问题的最优解如果可以由子问题的最优解推导得到,则可以先求解子问题的最优解,在构造原问题的最优解;若子问题有较多的重复出现,则可以自底向上从最终子问题向原问题逐步求解。

比如说著名的斐波那契定理a[i]=a[i-1]+a[i-2],就是一个特别好的理解方式,为什么直接写公式的算法(自底向上,从1开始递增)效率就是比递归(自顶向下,从n开始向下)的要好?

让我们来熟悉一下动态规划的特点:

a) 把原始问题划分成一系列子问题;

b) 求解每个子问题仅一次,并将其结果保存在一个表中,以后用到时直接存取,不重复计算,节省计算时间

c) 自底向上地计算。

d) 整体问题最优解取决于子问题的最优解(状态转移方程)(将子问题称为状态,最终状态的求解归结为其他状态的求解)

很简单,因为递归的方式return f(n-1)+f(n-2)会产生一些重复计算,当计算f(5)+f(4)中,f(5)其实又包含了一次f(4),而动态规划的出现,就是为了减少这样的重复计算,通过确认一个个的状态以及到达下一个状态的【状态转移方程】,来表现,一般而言,我们使用数学语言直接表示【状态转移方程】。

3. 分类

动态规划可以分为如下四大类,可以依次进行学习:

线性动规,区域动规,树形动规,背包动规。

4. 学习方法

一切的开始,都必须要勤记笔记,在最初的学习中,比如最大不下降子序列这题目,我们可以更具题意将题目要求,总结题目意思,发现是否选取这个序列数是一个状态,这个状态分为两种情况:选取,不选取,我们可以在草稿纸上面讲每一个状态利用一个二叉树画出来,然后推到出正确的方案,这是第一步,接着我们讲二叉树中的每一个数据提出,尝试着利用动态规划的思维,将这课树的状态转移方程提出,最后根据这个状态转移方程,写出最终的答案。

在熟悉相关类型的题目达到一定的程度的时候,自然得心应手。

5. 相关例题

可以直接从dotcpp网站标签中搜索动态规划即可,动态规划拥有海量的题目,非常适合深入理解和练习。


上一课:哈希算法 下一课:贪心算法
第一章 数据结构入门
第二章 链表
第三章 栈
第四章 队列
第五章 从C语言到C++
第六章 串,数组,矩阵,广义表
第七章 树
第八章 图
第九章 算法—查找
第十章 算法—排序
第十一章 算法&竞赛,思维培养
第十二章 后记