练习题(3) -- 另类的动态规划问题
版权声明 本站原创文章 由 萌叔 发表 转载请注明 萌叔 | http://vearne.cc 题目如下: 已知 对于数字1 可以表达为 (1) 对于数字2 可以表达为 (1,1) (2) 解释 1 + 1 = 2 对于数字3 可以表达为 (1,1,1) (1, 2) (2, 1) (3) 1 + 1 + 1 = 3 1 + 2 = 3 2 + 1 = 3 求对于数字N 所有表达项 解法提示: 这是一道比较简单的动态规划问题 对于数字3如果我们把它的所有表达想这样书写 以1为开头的序列的后半部分的和是2 动态规划有两个要素，一个是备忘录，一个是递推公式 我们可以得到如下递推公式 注意：这里的加号和乘号不表示数学意义的加发和乘法 准确的说* 号表示连接，+ 号表示f(n) 的表达项是这些表达项的集合 f (n) = 1 * f(n -1) + 2 * f(n -2) … … + (n-1) * f(0) ...