题目:给你一根长度为n的绳子,请把绳子剪成m段 (m和n都是整数,n>1并且m>1)每段绳子的长度记为k[0]k[1]...k[m]. 请问k[0]k[1]...*k[m]可能的最大乘积是多少?例如,当绳子的长度为8时,我们把它剪成长度分别为233的三段,此时得到的最大乘积是18.
思路:f(n)=max{f(i)f(n-i)},想发与实现是2个方法,想的时候是递归,实现的时候是从底层至最上面.
#绳子不断切割,当切割到长度为123时,不能继续切割,直接返回12.3
arr=[0123]#记录绳子长度为i时候的最大乘积arr[i]
maxs=0
实现:maxtmp记录临时子项和,遇到的每一个数不断累加;当maxtmp为负时,清空,从下一个数开始,从新累加;当累加的数大于maxsum时,将值赋给maxsum
还有一种暴力求解,双层遍历,复杂度O(n2)
把M个同样的苹果放在N个同样的盘子里,允许有的盘子空着不放,问共有多少种不同的分法?(用K表示)5,1,1和1,5,1 是同一种分法.
设f(mn) 为m个苹果,n个盘子的放法数目,则先对n作讨论,
当n<=m:不同的放法可以分成两类:
2,所有盘子都有苹果,相当于可以从每个盘子中拿掉一个苹果,不影响不同放法的数目,即f(mn) = f(m-nn).
而总的放苹果的放法数目等于两者的和,即 f(mn) =f(mn-1)+f(m-nn)
1.当n=1时,所有苹果都必须放在一个盘子里,所以返回1;
2.当没有苹果可放时,定义为1种放法;
递归的两条路,第一条n会逐渐减少,终会到达出口n==1;
第二条m会逐渐减少,因为n>m时,我们会return f(mm) 所以终会到达出口m==0
问要跳上第 n 级台阶有多少种跳法?
问要跳上第 n级台阶有多少种跳法?