整数拆分 先记录一下动态规划得思想:动态规划和分治法很像。分治法是把大问题拆分成小问题解决,但是小问题经常重复被解决,所以耗时很长;动态规划也是把大问题拆分成小问题,但是小问题都被记录下来,不会重复被解决,所以效率很高。动态规划的任务就是填表。填表的顺序是从左到右,从上到下,即这个表是个二维数组。以背包问题为例,在填写每一行时,随着列的增加,意味着背包的容量的增加;而在同一列中,随着行的增加,意味着在这个容量下(列不变)背包能装的东西的种类的增加(行变)。接下来我们来看一下这道题,输入一个数n,然后看看由2^0,2^1,2^2,...,2^n组成的方案一共有多少种。这就可以想成:我有一个容量为...