Java教程

算法——动态规划(DP)

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

一、例子

  以状态转移方程入手很难理解动态规划本身,下面用几个例子说明什么是动态规划。

1、n个1累加

  (1)1+1+1+1+1+1 = 6

  (2)1+1+1+1+1+1+1 = ?

  (3)1+1+1+1+1+1+1+1 = ?

   很快就能得出 (2)的结果是7,(3)的结果是8

   回忆得出结果的过程,我们并不是每次都从头到尾重新加,而是在已知 (1)的情况下,(2)的结果是 (1)的结果+1,同理 (3)是在 (2)的基础上+1。这就是最简单的动态规划,其特点如下:知道上一步骤的结果,把该结果交给当前步骤处理,得到的就是当前步骤的结果。

  这里会产生一个问题,即规划的方向,比如(2)的结果是根据(1)的结果得到,假如我们不知道(1),只知道最简单的“1 = 1”,则有以下两种做法

  A.从后往前,把问题无限拆分,回到“最简单”的那一项。把(1)再分解为某一个式子+1,不断地拆+1 出来,一直拆到 1 = 1 为止.

  B.从前往后,从“1 =1”开始,每一步 +1,直到满足要求。

 

2、斐波那契数列

  斐波那契数列有如下定义:

  f(0) = 0 

  f(1) = 1 

  f(n) = f(n-1) + f(n - 2)  ,  n>1

  求第n项?

  直观来想,假如我们想知道 f(10) ,那么我们就需要 f(9) 和 f(8) ,要知道 f(9) 则需要 f(8) 和  f(7) ,以此递归下去,最后一定会回到f(0) 和 f(1) 。这个特点与第一个例子中相同:知道上一步骤的结果,把该结果交给当前步骤处理,得到的就是当前步骤的结果。

  但这个例子和第一个例子有很大不同,f(n) = f(n-1) + f(n - 2)  , 所以斐波那契数列需要的“上一步”,本质上是“上一步”和“上上步”。而这两步又有重合的地方,如果我们采取从后往前递归的方式写程序,则会计算大量的重复结点。正确做法是从前往后:从“最简单”的一项开始,每处理一步,就记录当前步骤结果,并设置为上一步,再据此找下一步的答案,直到满足要求,采用循环结构。这样每一个结点都只会被计算一次。

 

3、青蛙跳台阶

  一只青蛙一次可以跳上1级 或 2级台阶,求跳上一个n级的台阶共有几种跳法?

  类似例2,如果最终要跳上10级台阶,那么上一次跳完可能在第9级,也可能在第8级,以此类推。题目暗示了“最简单”的子问题是跳1级和跳2级。我们需要把这个“最简单”的子问题考虑清楚。跳1级只有1种跳法,而跳2级有2种,即跳2次1级或1次2级。之后用例2中说的方法即可求解。

 

 

二、动态规划

 1.要求:

  • 知道上一步骤的结果,就能求出当前步骤的结果
  • 不断追溯上一步,可以回到一个“最简单”的子问题,该子问题必须是已知的
  • 每一步都基于同一种规则进行处理

 

  2.处理步骤

  1. 找“最简单”子问题,“最简单”子问题为开始递归时的第一个“上一步”
  2. 循环结构,循环体中描述每一步共用的处理规则,之后储存当前步的结果,将其作为上一步
  3. 循环结束,根据题目处理得到答案

 

  3.特征

  一般很难直接看出某个题是否可以用动态规划求解,但根据经验,能用动态规划的题一般符合以下特征:

  1. 统计类的问题,比如满足xx条件共有多少情况。也可能是求满足条件的某一项的问题。
  2. 这个问题一般要完成一个复杂的大任务,但这个大任务可以分成若干步骤,且各步骤都有若干决策,每个步骤完成后,就到达了一个阶段性状态,可以据此完成下一步。
  3. 题目可能会提示你:“答案可能会很大,请返回模 xxx 之后的结果”。动态规划每一步的结果是指数增长的,所以结果可能很大。关于取模:做题时有处理技巧: 先相加后取模 =  先取模后相加最后再取模  =  一个数取模一个数不取模,相加后再取模 。所以DP每一步记录取模后的结果即可,当然最后处理结果的时候别忘记取模。

 

 

 

三、一些比较复杂的DP问题

1.力扣2022.1.17每日一题 —— 1220.统计元音字母序列的数目

 

 

 

 

 

这篇关于算法——动态规划(DP)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!