Java教程

【算法】动态规划

本文主要是介绍【算法】动态规划,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

动态规划

1.概念

动态规划常用于的一个问题就是求最值, 比如说最常见的求最长递增子序列啊等待。

其实动态规划的问题核心仍然是穷举,想一下求最值,那最可能的就是把所有结果列出来,谁最大要谁。

动态规划大部分是自底向上的,所以也就脱离了递归,更多的是采用for循环的迭代;

动态规划的典型类型:
背包问题;
打家劫舍;
股票问题;
子序列问题;

动态规划常常用于求解多阶段决策问题
动态规划问题的问法:只问最优解(常和最值联系在一起),不问具体的解;

2.过程

动态规划类的题目我们一般情况下按照这三部曲进行:

  • 1.确定dp数组及其下标含义;
  • 2.确定递推公式,即状态转移方程;
  • 3.dp初始化,base case;

一般按照这三步后能够写出来一个程序,为了保险起见,我们可以带一个例子进去检验。

最关键的就是确定好dp的含义后去寻找递推关系;

3.样例

509. 斐波那契数

70. 爬楼梯

746. 使用最小花费爬楼梯

121. 买卖股票的最佳时机

64. 最小路径和

198. 打家劫舍

213. 打家劫舍 II

5. 最长回文子串

120. 三角形最小路径和

4.体会

  • 涉及到多决策的,之前想到的可能是用回溯,去构建一颗决策树;在不是平等的,比如说选1,2,3这样依次换着选一遍的情况时,我们很多情况下会去用动态规划,这和回溯的最大不同在于这里有一个很明确的递推关系,也就是状态转移,比如打家劫舍问题,或者是买卖股票等,dp数组在i时的状态能够由之前的递推出来
  • 很重要的一个点就是我们最初要明确好dp数组是干什么的,下标还有它本身的意义是什么。
  • 要找到base case ,也就是把dp数组初始化好。
这篇关于【算法】动态规划的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!