admin 管理员组文章数量: 894082
动态规划法——常见题型及算法思路
有关动态规划类问题本书不够入门,内容较严谨,不太适合小白,在此我将写下一些动态规划的基础思想(基础不代表简单,只是需要的前备知识少)。
使用动态规划法求解整数拆分问题
下面是逻辑推理的过程(动态规划方程的理由),只是为了方便理解规划方程的原因才硬写出来的。
即使不知道原因,也能写出动态规划方程,不用理由。有基础的可以跳到下方红线处。
该题目中n代表数值,k代表最多能被拆成多少组
n=4,k=4:
4—1+1+1+1
2+1+1
3+1
4
-------------------------------------------------------
n=4,k=3:
4—2+1+1
3+1
4
---------------------------------------------------------
n=4,k=2:
4—3+1
4
------------------------------------
n=4,k=1:
4—4
-----------------------------------------------
n=1,k=3:(1虽然可以允许最多被分成3个,由于1只能分成1个,因此n=1时k=2时与k=1时结果没区别)
1—1
n=2,k=2:
2—1+1
2
n=2,k=3:(2虽然允许被分成3个但2最多能被分成2个数,因此n=2时k=3与k=2没区别)
2—1+1
2
n=3,k=3:
3—1 +1+1
2+1
3
n=3,k=2:
3—2+1
3
n=3,k=1:
3—3
***********************************************************************************************************
***********************************************************************************************************
该问题中要求求解整数拆分:
N表示要拆分的数字,k表示最多能被拆成k个的所有情况
根据上面题目
书中如此解释:
1.当n=1或k=1(k=1表示这个数最终只能被分成一个数字,那就是说不能拆,也就是它自己)
因此f(n==1 || k==1)=1
2.当k>n时(例如允许2 ,拆成3个数;允许3, 拆成4个数,跟允许2分成2个数,允许3分成3个数,没区别,因为大小为n的数最多被拆成n个数)
因此f(k>n)=f(k=n)
3.当k=n时
如图:
发现了吗?f(n,n)所组成的方法数比f(n,n-1)多出来1个方案(多出来的1个方案是全部都由1组成的方法)
因此可得规律:
N=k时,f(n,n)=f(n,n-1)+1
4.当k<n时。。。balabala在此不建议看书上了,我明明白白告诉你,那个理由是作者弄出答案之后硬掰出来的。为的是让自己写的书看起来逻辑完美。笔试时压根不会给你时间深究原理。)
下面是做动态规划求解此题的真正做法:
设f(n,k)为n的k拆分的拆分方法数
N表示要拆分的数字,k表示最多能被拆成k个的所有情况
打表(根据算出来的解,填表)如下
因此,
可得出规律:f(n,k)=f(n-k,k)+f(n,k-1)
同样根据表中规律可得出:
动态规划步骤就这么简单,算出前面几个解后,填表,找规律,就能求出解,
真正的难点在于试法(这个表该怎么画,是应该一维的还是二维的,变量要怎么选,要选几个),清楚了如何去试之后,解题就没什么难点,后面重点就是优化了。
本文标签: 动态规划法常见题型及算法思路
版权声明:本文标题:动态规划法——常见题型及算法思路 内容由网友自发贡献,该文观点仅代表作者本人, 转载请联系作者并注明出处:http://www.freenas.com.cn/jishu/1687604957h120224.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
发表评论