动态规划

计数DP实例讲解

计数DP实例讲解本篇主要从计数DP上结合实例分析。一、计数类DP——整数划分整数划分大体上可以分为3类(1)考虑顺序的拆分方案(即1,1,2;和2,1,1是两种不同的方案),这种问题一般转化为……

数位DP概念和实例讲解

数位DP概念和实例讲解说到数位DP,它主要是用于处理一些与数位有关的问题,主要是计数问题。并且数位DP一直以来是DP家族里比较冷门的一种,但一旦遇上了,如果不会数位DP单纯靠暴力方法很难骗分。一、什么是数位DP?数位DP是……

线性DP图文实例讲解

线性DP图文实例讲解线性DP,所谓线性DP,就是指我们的递归方程有一个明显的线性关系的,有可能是一维线性的,也可能是二维线性的。例题一:大盗阿福题目:阿福是一名经验丰富的大盗。趁着月黑风高,阿福打算今晚洗劫一条街上的店铺……

什么是记忆化搜索?

什么是记忆化搜索?首先大家要知道,记忆化搜索是动态规划的入门。什么是记忆化搜索?搜索的低效在于没有能够很好地处理重叠子问题;动态规划虽然比较好地处理了重叠子问题,但是在有些拓扑关系比较复杂的题目面前,又显得无奈。记忆化……