和大白一起学动态规划(一)

问题描述

给定正整数n，找出所有不同的写法使得n为整数1，3，4的和。

如：n=5时，不同的写法有6种。

5      = 1+1+1+1+1

       = 1 + 1 + 3

       = 1 + 3 + 1

       = 3 + 1 + 1

       = 1 + 4

       = 4 + 1

问题分析

从初中开始我们就接触了函数的概念，所谓函数指的就是给定自变量x，根据某种映射规则进行运算后，会得到一个值y。

举个简单的例子来说明，y=2·x就是一种映射关系，如给定x=2，进行运算后可以得到y=2·2=4。

而上述提到的问题，就是某种映射关系，只不过这种映射关系，我们目前还不知道具体是什么，需要我们去探索去解决。

假设现在已经知道了这种映射关系，即给定任意的正整数x，可以有y种符合要求的写法，即f(x) = y。

而示例给出的正是f(5) = 6，表示的是给定正整数5，符合要求的写法有6种。

接下来考虑计算正整数n的写法，即f(n)。

设n的一种可能的写法为：n = x₁+x₂+···+x_m

我们从x_m这一项入手，考虑其有几种不同的写法，根据题意，x_m可能的值为1，3，4，因为每一项只能出现1，3，4。

令x_m = 1，则:

n = x₁+x₂+···+x_m-1+ 1    （移项）

n-1 = x₁+x₂+···+x_m-1

通过上面的计算得出，当x_m=1时，要计算正整数n的写法，就转化为求正整数n-1的写法即f(n-1)种。

以此类推，令x_m = 3，则：

n = x₁+x₂+···+x_m-1 + 3

n-3 = x₁+x₂+···+x_m-1

问题转化为求n-3的写法即f(n-3)种。

令x_m = 4，则：

n = x₁+x₂+···+x_m-1 + 4

n-4 = x₁+x₂+···+x_m-1

问题转化为求n-4的写法即f(n-4)种。

因此我们将上面的三种写法综合起来即得到：f(n) = f(n-1) + f(n-3) + f(n-5)。即要想求得正整数n的写法，我们需要先指导n-1, n-3和n-5这三个整数的写法，然后求和即可。

总结

本文通过一个简单的案例，介绍了函数的基本思想，并将其应用到解决问题的思路中，帮助大家深入的理解函数。