您的位置:首页 > 博客中心 > 互联网 >

动态规划基础

时间:2022-05-11 09:11

技术分享图片

技术分享图片

技术分享图片

技术分享图片

 

n扩大两倍,时间扩大了2w倍。

时间复杂度非常大!指数级!

 

技术分享图片

 

大量的重复计算。能不能只算一次呢?

 

通过全局变量的数组,记录计算过的数字。

技术分享图片

 

 空间换时间。

记忆化搜索

技术分享图片

原来

技术分享图片

 

记忆化搜索和递归都是,自上而下的解决问题。

假设基本问题已经解决。

 

技术分享图片

递推公式。

动态规划其实比递归更快,因为减少了函数的调用,并且memo每个元素只调用了一次。

 

技术分享图片

 

 技术分享图片

 

先记忆化搜索找出解法,再转化为自底向上动态规划的解法

本类排行

今日推荐

热门手游