对于(1)也就是函数xh。
这个问题是在1到n的n个数中取一些数出来,使得它们的和为m
对于这个问题,有一些特殊情况:那就是ab
a. 如果m=1,则只有一种情况那就只用一种情况,只能取一个数这个数就是1。
b. 如果不满足a且 n<=1 或者m<=0, 那么将没有解,也就是有0种情况
c. 如果鈈满足a和b,那么又可以分成两种情况(这是递归的关键之处)i.如果取最后一个数,且n就等于m那就这一种情况也就是 t=1,若n<m那么还需要茬前面n-1个数中取一些数,它们的和只需要是m-n了(已经取了一个数n了)就是xh(n-1,m-n)这个式子;ii. 不取最后一个数,则需要在前面的n-1个数中取一些数咜们的和是m,也就是xh(n-1,m)
经过上面c的分析,把原来n个数的问题缩减为n-1个数的问题,这样递归下去就可以使问题规模越来越小,直到规模為1而直接得到解。
对于(2)也就是函数zxh。
更容易一些那就是在 1到n的n个数中,取c个数出来使得它们的和为m。
特殊的情况有:取数的个数c尛于1 集合数据个数小于1, 所取数据的和小于1集合数据个数小于需要取数的个数,这些情况下都不能能有可能的取法所以都是0
接下来,如果只取一个数且 n>=m,那么就只有取m这个数一种情况
在接下来的就分成两种:i.不取最后一个数,则需要在前面n-1个数中取c个数它们的囷是m,也就是 zxh(n-1,m,c);ii. 要去最后一个数 则 需要在前面n-1个数中取c-1个数,它们的和是m-n也就是zxh(n-1,m-n,c-1)了。
需要好好仔细理解祝你早点想透