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)nk拆分的拆分方法数

N表示要拆分的数字,k表示最多能被拆成k个的所有情况

打表(根据算出来的解,填表)如下

因此,

可得出规律:f(n,k)=f(n-k,k)+f(n,k-1)

同样根据表中规律可得出

动态规划步骤就这么简单,算出前面几个解后,填表找规律,就能求出解,

真正的难点在于试法(这个表该怎么画,是应该一维的还是二维的,变量要怎么选,要选几个),清楚了如何去试之后,解题就没什么难点,后面重点就是优化了。

本文标签: 动态规划法常见题型及算法思路