整数划分（三连发）

整数划分第一题：点击打开链接NYOJ90

整数划分第二题：点击打开链接NYOJ176

整数划分第三题：点击打开链接NYOJ571

第一题：

1 样例：如一个正整数5，可以划分为7种：

[5]
[4,1]
[3,2] [3,1,1]
[2,2,1] [2,1,1,1]
[1,1,1,1,1]

2分析：2

将一个正整数n划分，共有多少种划分方式？
上面的例子第一行，所有加数不超过5；
第二行，所有加数不超过4；
........
第五行，所有加数不超过1.
定义 dp[n][m]表示正整数n，所有加数不超过m的划分数目。

3分析m，n：
1、n== 1或m== 1时共1种划分方式dp[n][m] = 1;
2、n== m时dp[n][n]= dp[n][m-1]+1，这样就把主要问题转化为对3的分解。
3、n> m时我们发现只要将dp[n][m-1]加上包含加数m的划分数就等于dp[n][m]。即：dp[n][m]= dp[n][m-1] +包含加数m的划分数。
包含加数m的划分数可以转化为：dp[n-m][m]。所以3可以表示为：
dp[n][m]= dp[n][m-1] + dp[n-m][m]
4、n< m等同于dp[n][n];

4代码：

1 样例：5分成2个正整数的和有2种
               1 4
               2 3
2分析：
定义dp[n][m]表示的是将n分成m部分的方案数，那么这个时候就考虑这个m部分的组成情况
1如果这m部分没有1，那么我们先将m个1分到m份上面，然后在将剩下的n-k分到m部分上，所以就有dp[n][m] = dp[n-m][m];
2如果这m部分有1，那么先将1这个部分扣除，剩下的就是n-1分给m-1部分了，
所以就有dp[n][m] =dp[n-1][m-1];
所以就有dp[n][m]= dp[n-m][m] + dp[n-1]][m-1]；
3注意事项：
当n= m时候dp[n][m]= 1;
当 m= 1时候dp[n][m]= 1;
当 n= 1时候n< m那么dp[n][m]= 0；
4代码：