网站搭建完手机访问,ppth5怎么制作,音乐制作网站,yandex引擎搜索入口史上最容易理解的暴力递归和动态规划~~介绍递归和动态规划暴力递归#xff1a;1#xff0c; 把问题转化为规模缩小了的同类问题的子问题2#xff0c; 有明确的不需要继续进行递归的条件(base case)3#xff0c; 有当得到了子问题的结果之后的决策过程
4#xff0c; 不记录… 史上最容易理解的暴力递归和动态规划~~介绍递归和动态规划暴力递归1 把问题转化为规模缩小了的同类问题的子问题2 有明确的不需要继续进行递归的条件(base case)3 有当得到了子问题的结果之后的决策过程
4 不记录每一个子问题的解区别于动态规划2动态规划1 从暴力递归中来2 将每一个子问题的解记录下来 避免重复计算3 把暴力递归的过程 抽象成了状态表达
4 并且存在化简状态表达 使其更加简洁的可能 动态规划其实是由暴力递归演变而来的每个动态规划的接法基本都能找到其动态规划的版本~
他们的关系如下
暴力递归------》依赖关系套路即记忆关系------》动态规划下面以一道题为例子来向大家详细的介绍一下先理解一下题意
给定一个数组和一个整数可以随便选择arr数组里面的数字看看累加起来能不能得到aim可以得到就返回true不可以返回false
eg arr[] { 3, 2, 9, 7 }; Aim 21;返回true 329721arr[] { 3, 2, 9, 7 }; Aim 13;返回false无法组合得到13思路分析
先用暴力递归的方式来解决先看一下方法的参数参数有arr[]和Aim是题目提供的我们自己定义的有i和sum这两个参数是什么意思呢
他们的含义是在一个数组中从i下标开始可以任意去i后面的数进行累加累加的和为sum看图如果你能想到这个图或者说看到这个图你就已经成功了一半~~
可以发现要判断这个数组中是否有满足要求的组合只要看最后一行是否有相应的aim值就可以了。
所以就有了下面的暴力递归暴力递归之后就是动态规划了~
来来来重点来了从暴力递归转变到动态规划跟题意是没有半毛钱关系的~
下面划重点了
暴力递归------》依赖关系套路即记忆关系------》动态规划
这里还差了个依赖关系
啥都别说了先画个图吧嘻嘻~
还是以上面那个例子为主
arr[3] {2,3,7};
aim 10;
那么i的取值范围就是0~3了
sum的取值则是23712即0~12
先看暴力破解法的basecase辣么第三行sum等于Aim的值就为true其他为false
再看基本关系通过细细分析可以得到下面的依赖关系图了~
图中的方框加×是isum的依赖也就是说要想得到Isum的值只要知道两个方框加×里面的值就可以推出来了 不是我说的是程序里面体现出来的那么因为第三列的值都知道了那么其他列的值肯定也可以通过这一列的值推出来那么我们所要求的00的值不就出来了吗这个依赖关系出来之后那么动态规划的解也就出来了~~~开心其实这个方法我也是思考了很久才领悟的~
希望对你们也能有所帮助~~不懂欢迎留言懂得帮忙点个赞~~~
