MOOC学习递归中涉及动态规划部分经典题目

2017-07-14更新放苹果问题:参考http://www.cnblogs.com/wxgblogs/p/5742618.html
放苹果
设函数f(M,N)为把M个同样的苹果放在N个同样的盘子里,允许有的盘子空着不放的分法的数量。(5,1,1和1,5,1 是同一种分法。)
求该函数的递推式
解答:

1
2
3
4
5
f(m,n)={
m==0||n==1 -> 1;
m<n -> f(m,m); //将m个苹果装到多于m个的盘子中必定不能装满,所以把m个苹果装到m个盘子里就好
m>=n -> f(m-n,n) + f(m,n-1); //分成两种情况,f(m-n,n)是没有空盘子:把n个盘子里每个都装上一个苹果,剩下的m-n个苹果再装到n个盘子里;f(m,n-1)是有空盘子,把那一个不装扔出来就好。
}

简单的整数划分问题
将正整数n 表示成一系列正整数之和,n=n1+n2+…+nk, 其中n1>=n2>=…>=nk>=1 ,k>=1 。正整数n 的这种表示称为正整数n 的划分。正整数n 的不同的划分个数称为正整数n 的划分数。设函数f(m,n)为将整数m划分为每个数最大为n的划分数。
求该函数的递推式
解答:

1
2
3
4
5
6
f(m,n)={
m==1|| n==1 -> 1; //m==1时,只能分成1个1;n==1时,只能分成m个1。
m<n -> f(m,m); //n>m时,将n调至m
m==n -> 1+f(m,n-1); //当m==n时,因为整数m可以自己算作一个划分,那么就要把n-1传递下去
m>n -> f(m-n,n)+f(m,n-1); //m>n时,可以在当前状态下分出去n或者不分出去n,对应两个f();
}

分解因数
给出一个正整数a,要求分解成若干个正整数的乘积,即a = a1 * a2 * a3 * … * an,并且1 < a1 <= a2 <= a3 <= ... <= an,问这样的分解的种数有多少。注意a = a也是一种分解。 解答:设函数f(m,n)为将整数m划分成小于等于整数n的划分数。

1
2
3
4
5
6
f(m,n)={
n==1 -> 0; //划到1就不能再往下分了
m==1 -> 1;
m%n==0 -> f(m/n,n) + f(m,n-1); //当m可以整除n的时候,可以除完了划分下去,也可以不除
m%n!=0 -> f(m,n-1); //只能不除
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注