更多优质内容
请关注公众号

算法小白的入门日记(三十五)动态规划-张柏沛IT博客

正文内容

算法小白的入门日记(三十五)动态规划

栏目:算法专题 系列:算法小白的入门日记 发布时间:2022-01-29 23:05 浏览量:230
本系列文章目录
展开/收起

· 动态规划概述

动态规划(Dynamic programming,简称 DP)不是某一种具体的算法,而是一种算法思想:若要求解一个给定问题,我们需要先解其子问题,再根据子问题的解得出原问题的解。

 

· 动态规划要点

1、首先动态规划问题的一般形式就是求最值

2、因为要求最值,肯定要把所有可行的答案穷举出来,然后在其中找最值。所以求解动态规划的核心是穷举

3、穷举的过程中可能存在重叠子问题,因此暴力穷举的话效率会极其低下,需要一个起到备忘录作用的DP表来记录所有穷举过的结果,避免重复计算。DP表不仅是一个备忘录,还是一个最终结果,是题目所需的解。

4、若要得到原问题的最优解,就需要在定义最优子结构的情况下先得到子问题最优解,因为原问题的最优解是建立在子问题最优解为基础的。

5、“如何定义子问题才能通过子问题的解得到原问题的解”这叫做定义最优子结构。如果定义子问题都定义错了,即使得到了子问题的最优解,也无法转为原问题的最优解。

定义最优子结构之后,“如何把求解原问题的解转为求解子问题的解”,这就涉及到状态转移方程,该方程能帮助我们把原问题转为子问题(如果定义的子结构不是最优的,或者说定义的子结构不对,那么得到的状态转移方程也是错误的)。

6、动态规划可以使用自底向上(迭代)或者自顶向下(递归)2种方式解决。使用自底向上(迭代)解题比用自顶向下(递归)的效率高,因为递归需要将函数使用到的临时变量压栈,占用空间更多,空间复杂度更高。

 

一个问题有什么「状态」,有什么「选择」,然后穷举,这就是动规的思路。

 

 

 

· 动态规划思想经典案例

 

斐波那契数列

题目如下:求n=20的斐波那契数列值。

 

斐波那契数列规律如下

           {

f(n) =         1, n∈{1,2}

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

             }

 

斐波那契数列代码实现:

func fib(n int) int {
    if n <= 2{
        return 1
    }
    return fib(n-1) + fib(n-2)    // 是一个二叉树的后序遍历
}

 

 

这种写法其问题在于复杂度太高,当n=20的时候,花费的时间很久。我们可以画出递归树分析一下其复杂度:

 

递归树的每个节点代表一次递归函数的调用。fib(n)的复杂度等于 递归次数 * 每次递归的复杂度。

fib(n)内部只有一个加法运算和 if判断,因此单次递归的复杂度为O(1)。

递归树的树高为 n = 20 层,共有约 2^0 + 2^1 + ... 2^19 = 2^20 - 1个节点,因此会发生2^n-1次递归调用。

综上,每次递归的复杂度为O(1),共 2^n - 1次递归,因此总体复杂度为 O(2^n)。

这是一个指数级的复杂度。

 

下面介绍如何优化fib算法。

 

- 减少计算规模

我们可以看到递归树中有很多的重复节点(如下图标有颜色的节点),因此可以在递归的过程中使用一个dp表记住每次递归的结果,在下一次遇到相同的递归调用时,从dp表查结果直接返回即可。

例如 左侧fib(18)的结果记录到dp表之后,右侧的fib(18)就不会重复计算,而是读取dp表内的结构,如此一来右侧fib(18)节点下的所有节点都无需计算,相当于剪枝。

 

代码实现如下:

var dp []int
func fib(n int) int {
    if n == 0{
        return 0
    }
    dp = make([]int, n+1)
    return fibHelper(n)
}
func fibHelper(n int) int{
    if n <= 2{
        dp[n] = 1
        return 1
    }
    if dp[n] != 0{
        return dp[n]
    }
    dp[n] = fibHelper(n-1) + fibHelper(n-2)
    return dp[n]
}

 

使用了dp表之后,dp[1]~dp[19]会在遍历递归树的最左侧路径时全部算好,整个递归树退化为一个链表(下图橙色部分所示),复杂度从O(2^n)优化为O(n)。

打了×的分支都不用重复计算。

带dp备忘录的递归算法把一棵存在巨量冗余的递归树通过「剪枝」,改造成了一个不存在冗余的链表,极大减少了子问题(即递归图中节点)的个数。

 

本题的解题方式是自顶向下(递归法)

为什么叫自顶向下,因为上面代码的计算顺序是从fib(20)开始一直到fib(1)和fib(2)(从递归树中也可以直观的看出是自顶向下的遍历顺序)。

而dp表的构建是自底向上的,例如要知道dp[20]就要先知道dp[18]和dp[19],要知道dp[18]就要先知道dp[17]。因此肯定要先得出递归树中所有子节点的dp值才能得到父节点的dp值,因此dp表的构建肯定是一个后序遍历,dp[k]的赋值是放在所有子节点递归之后的位置发生的。

此外DP表不仅是一个备忘录,也是一个结果表,是题目最终答案。

 

本题同样可以使用自底向上(迭代法)完成,实现从dp[1] -> dp[20]的顺序的构建dp表。

代码实现如下:

func fib(n int) int {
    if n == 0{
        return 0
    }
     if n <= 2{
        return 1
    }
    dp := make([]int, n+1)
    dp[1], dp[2] = 1,1
    for i:=3; i<=n; i++{
        dp[i] = dp[i-1] + dp[i-2]
    }
    return dp[n]
}

 

此外 fib(n)只需依靠n的前两个值计算,因此dp表无需记录1~n的所有结果集,只需记录最近的两个数n-1和n-2的结果即可。所以可以将dp表从一个一维数组压缩成2个普通变量,空间复杂度从O(n)优化为O(1)。

func fib(n int) int {
    if n == 0{
        return 0
    }
     if n <= 2{
        return 1
    }
    dp := make([]int, 2)
    dp[0], dp[1] = 1,1
    for i:=3; i<=n; i++{
        dp[0], dp[1] = dp[1], dp[0] + dp[1]
    }
    return dp[1]
}

 

 

“斐波那契数列”这个例子涉及到动态规划的2个关键点:状态转移方程和重叠子问题。

状态转移方程 就是当前问题fib(n) 和 子问题 fib(n-1) 的关系式:

    	{
f(n)   = 	    1,  n∈{1,2}
  		    f(n-1) + f(n-2), n > 2
    	}

 

重叠子问题 就是递归树中存在需要重复计算的树节点。可用dp表解决。

 

由于斐波那契数列没有涉及子问题最优解,因此严格来说,它不算一个动态规划问题,但是它用到了动规的思想。

 

 

下面我们再看一个经典的动态规划案例。

力扣322. 零钱兑换

给你一个整数数组 coins ,表示不同面额的硬币;以及一个整数 amount ,表示总金额。

计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额,返回 -1 。

你可以认为每种硬币的数量是无限的。

动规题无论用迭代法还是递归法,关键是要把自变量(原问题)的规模不断缩小,找到本问题和子问题的关系(即状态转移方程)。

在本题中,以示例1为例,原问题 amount = 11 所需的最少硬币数 等于 amount = 11 - 1 = 10 或者 amount = 11 - 2 = 9 或者 amount = 11 - 5 = 6 这3个子问题所需的最少硬币数 + 1。

x的最优解 f(x) 等于 min(f(x-m)) + 1,其中 m 是coins中的某个面值,由于m有len(coins)种情况,所以我们需要找出 f(x-m)的最小值。

综上,得到状态转移方程为:

 

迭代法(python实现):

class Solution:
    def coinChange(self, coins, amount):
        res = [0]  # res长度为amount+1
        coins.sort()
        for i in range(1, amount + 1):
            minNum = amount + 1  # 子问题中所需最少的硬币数
            for coin in coins:   # 子问题的个数为len(coins)
                smallerAmount = i - coin  # 子问题
                if smallerAmount < 0:
                    break
                if res[smallerAmount] != -1 and res[smallerAmount] < minNum:  # res[smallerAmount] == -1表示smallerAoumut这个子问题无解
                    minNum = res[smallerAmount]

            minNum = -1 if minNum == amount + 1 else (minNum + 1)
            res.append(minNum)
        return res[-1]

 

递归法(go实现):

var dpCoins map[int]int
var coinsMap map[int]struct{}
func coinChange(coins []int, amount int) int {
   if amount == 0{
      return 0
   }
   sort.Ints(coins)
   dpCoins = make(map[int]int)
   coinsMap = make(map[int]struct{})
   for i:=0; i<len(coins); i++{
      coinsMap[coins[i]] = struct{}{}
   }
   return coinChangeHelper(coins, amount)
}

func coinChangeHelper(coins []int, amount int) int{
   if amount == 0{
      return 0
   }

   if coins[0] > amount{  // 如果amount小于最小面值
      dpCoins[amount] = -1
      return -1
   }

   if _, ok := coinsMap[amount]; ok{  // 如果amount不是某个面值
      dpCoins[amount] = 1
      return dpCoins[amount]
   }

   if _, ok := dpCoins[amount];ok{       // 不重复计算
      return dpCoins[amount]
   }

   dpCoins[amount] = -1
   for i:=len(coins) - 1; i >= 0; i--{
      if coins[i] < amount{
         tmp := coinChangeHelper(coins, amount - coins[i])
         if tmp != -1 && (dpCoins[amount] == -1 || dpCoins[amount] > tmp+1){       // 如果 amount - coins[i]的解为 -1 不代表 amount的解为-1,需要继续循环
            dpCoins[amount] = tmp + 1
         }
      }
   }
   return dpCoins[amount]
}

 

 

· 动态规划总结

动态规划问题的一般形式就是求最值。动态规划的解题思路本质是穷举(每次递归都在做选择),并去除重叠子问题。动规问题可以具象为一个递归树结构。

 

动规的3要素:

    最优子结构(即怎么定义dp表,或者怎么定义怎么解释递归函数)

    重叠子问题(用dp表记住已处理的情况,不重复处理相同的情况,相当于对递归树剪枝)

    状态转移方程(如何通过已处理过的问题得到当前问题的解,即当前问题和子问题之间的关系)

 

动规问题的2种解决方法:

    自底向上(迭代)

    自顶向下(递归)

 

动规问题的空间优化:

    对dp表状态压缩(二维数组压缩为一维,一维数组压缩为单个整数变量)

 

 

· 贪心算法

贪心算法的思想是:每一步都做出一个局部最优的选择,最终的结果就是全局最优。只要满足这个条件,就能使用贪心算法求解。

贪心算法本身是动态规划的一种,但性能更优于普通的动态规划,动态规划的复杂度为多项式级别,而贪心算法的复杂度可以在普通动态规划的基础上优化为线性级别。

 

解决一个问题需要多个步骤,每一个步骤有多种选择,这样的描述我们在「回溯算法」「动态规划」算法中都会看到。

贪心算法是动态规划的一种特殊情况,或者说是动规的优化。它和动规的相同点在于:规模较大的问题的解由规模较小的子问题的解组成。

区别在于:可以使用「贪心算法」来解决的问题,其「规模较大的问题的解」只由其中一个「规模较小的子问题的解」决定;

说简单点就是,动规问题每一步都有多个可能的选择,需要尝试多个可能的选择才能知道哪个选择更优;而贪心算法问题,每一步只有一个已知可以达到最优的选择,体现为递归树的一条分支。

 

贪心算法的经典问题可以参考 力扣-贪心算法问题集合

 

下面以一道题目为例。

435. 无重叠区间

给定一个区间的集合,找到需要移除区间的最小数量,使剩余区间互不重叠。

注意:

可以认为区间的终点总是大于它的起点。
区间 [1,2] 和 [2,3] 的边界相互“接触”,但没有相互重叠。

 

这个问题在生活中的应用广泛,比如你今天有好几个活动,每个活动都可以用区间[start,end]表示开始和结束的时间,请问你今天最多能参加几个活动呢?

如果你学过算法,就可以比别人更高效地规划时间。

 

正确的思路其实很简单,可以分为以下三步:

  1. 先将所有区间按照start升序排序,用两个指针p1和p2指向排序后的区间集合中的前两个区间,即 p1, p2 = 0, 1。区间p1是在当前所有区间中start 最小的区间。之所以排序是为了让start相近的区间聚集在一起,方便比较,start约相近的区间也可能发生相交。

  2. 判断 p1 和 p2 这两个start临近的区间是否相交,如果相交则判断p1和p2他们谁的end比较大,删除那个end比较大的区间,因为end越大的区间,越可能和其他后面的区间(即start比x和y大的区间)重合,被删除的区间指针往后移。如果p1和p2不相交,则p1和p2都往后移。保持p2指针位于在p1指针的右边。

  3. 重复判断p1和p2区间是否相交,直到p2到达最后一个区间。

 

代码实现

import "sort"

func eraseOverlapIntervals(intervals [][]int) int {
	newIntervals := _intervals(intervals)
	sort.Sort(newIntervals)
	deleteNum := 0
	p1, p2 := 0,1
	for  p2 < len(newIntervals){
		if _isCross(newIntervals[p1], newIntervals[p2]){
			if newIntervals[p1][1] > newIntervals[p2][1]{	// 删除p1所指的区间
				p1 = p2
                p2++
			}else{	// 删除p2所指的区间
				p2++
			}
			deleteNum++
		}else{
			p1 = p2
			p2++
		}
	}
	return deleteNum
}

// 判断两个区间是否相交
func _isCross(a1, a2 []int) bool{
	if a1[0] <= a2[0] && a1[1] > a2[0]{
		return true
	}

	if a1[0] >= a2[0] && a2[1] > a2[0]{
		return true
	}
	
	return false
}

type _intervals [][]int
func (this _intervals) Len() int {return len(this)}
func (this _intervals) Less(i, j int) bool {return this[i][0] < this[j][0]}
func (this _intervals) Swap(i, j int) {this[i], this[j] = this[j], this[i]}

 




更多内容请关注微信公众号
zbpblog微信公众号

如果您需要转载,可以点击下方按钮可以进行复制粘贴;本站博客文章为原创,请转载时注明以下信息

张柏沛IT技术博客 > 算法小白的入门日记(三十五)动态规划

热门推荐
推荐新闻