问题描述
给定正整数n，找出所有不同的写法使得n为整数1，3，4的和。
如：n=5时，不同的写法有5种。
解决方案
下面将介绍利用动态规划的思路来解决问题。
1、 将问题求解转化为函数形式。
从初中开始我们就接触了函数的概念，所谓函数指的就是给定自变量x，根据某种映射规则进行运算后，会得到一个值y。
举个简单的例子来说明，y=2·x就是一种映射关系，如给定x=2，进行运算后可以得到y=2·2=4。
而上述提到的问题，就是某种映射关系，只不过这种映射关系，我们目前还不知道具体是什么，需要我们去探索去解决。
假设现在已经知道了这种映射关系，即给定任意的正整数x，可以有y种符合要求的写法，即f(x) = y。
而示例给出的正是f(5) = 6，表示的是给定正整数5，符合要求的写法有6种。
2、分析递推情况。
接下来考虑计算正整数n的写法，即f(n)。
设n的一种可能的写法为：n = x1+x2+···+xm
我们从xm这一项入手，考虑其有几种不同的写法，根据题意，xm可能的值为1，3，4，因为每一项只能出现1，3，4。
令xm = 1，则:
n = x1+x2+···+xm-1+ 1 （移项）
n-1 = x1+x2+···+xm-1
通过上面的计算得出，当xm=1时，要计算正整数n的写法，就转化为求正整数n-1的写法即f(n-1)种。
以此类推，令xm = 3，则：
n = x1+x2+···+xm-1 + 3
n-3 = x1+x2+···+xm-1
问题转化为求n-3的写法即f(n-3)种。
令xm = 4，则：
n = x1+x2+···+xm-1 + 4
n-4 = x1+x2+···+xm-1
问题转化为求n-5的写法即f(n-4)种。
因此将上面的三种写法综合起来就得到求解正整数n的写法有：f(n) = f(n-1) + f(n-3) + f(n-4)。即要想求得正整数n的写法，我们需要先知道n-1, n-3和n-4这三个整数的写法，然后求和即可。
3、代码实现。
下面将介绍python的代码实现部分。
import numpy as np
MAX_N = 10
# 给定正整数n，找出所有不同的写法使得n为整数1，3，4的和。
dp = np.zeros((MAX_N,))
dp[1] = 1
dp[2] = 1
dp[3] = 2
dp[4] = 3
dp[5] = 5
for i in range(6, MAX_N):
dp[i] = dp[i - 1] + dp[i - 3] + dp[i - 4]
print(dp)
结语
本文通过一个简单的凑整数案例，介绍了函数的基本思想，并将其应用到解决问题的思路中，帮助大家深入的理解函数。利用动态规划的思路分析问题、解决问题并最终完成了python代码的编写。
拓展阅读：
深入理解遗传算法(一)深入理解遗传算法(二)从1到100求和学算法思维（一）从1到100求和学算法思维（二）从1到100求和学算法思维（三）从1到100求和学算法思维（四）从1到100求和学算法思维（五）从1到100求和学算法思维（六）where2go 团队
微信号：算法与编程之美
本站仅提供存储服务，所有内容均由用户发布，如发现有害或侵权内容，请
点击举报。
