http://zhidao.baidu.com/question/105790100.html

一个组合数学的问题。

写了不少程序，还没仔细思考过这个问题，今天花了不少时间来想，上面的连接有些帮助。


这题目求的是一个整数n拆分长度为k时的拆分数，200的规模显然只有递推。

有如下递推式： D(n,k)=∑D(n-k,i),1<=i<=k, 

D(n,k)指 整数n拆分长度为k时的拆分数 ，其中D(0,0)=1

解释起来也挺容易的，也就是dp的思想，solve problem from subproblems.


很有意思的是，递推式或者数学式往往并不是那么简单的，它同时可能包含多种解释。
当上面的k解释成最大数时（拆分时最大的一项，不能被超过），递推式同样成立，但整个含义就变了。
他们之间的关系是暗含的，这里引用一段-“将整数r拆分为k个正整数的拆分数,等价于将r拆分为最大数为k的拆分数.证明略,你有兴趣可以去搜索下费勒斯图像.”。


在上面的过程中还领悟到了，组合数-“从n个不同的东西中选择m个”的选法C(n,m)与“把n个相同的东西放到m个相同的盘子里”的放法P(n,m)也是存在暗含的关系，P(n,m)=C(n-1,m-1)


出现这样状况的原因，可解释为：同样的本质，不同的表象。

数学是本质的，它代表了很多很多的现象....sigh... 

• Re:都是猛人，动动脚趾就ac了，sigh~ (27) ip96cns 2010-12-07 19:35:43
• Re:都是猛人，动动脚趾就ac了，sigh~ (66) lxyxynt 2011-03-03 22:40:57
  • Re:都是猛人，动动脚趾就ac了，sigh~ (320) 1120131925 2014-10-13 00:39:44