1. 问题描述
给定正整数n，找出所有不同的写法使得n为整数1，3，4的和。
如：n=5时，不同的写法有6种。
2. 问题分析
下面将介绍利用动态规划的思路来分析并解决问题。
第一步：对题目描述问题进行建模，将其转化为函数形式描述。
利用函数的思想对问题进行建模，令y=f(x)表示满足题目要求的正整数x有y种不同的写法。则f(5)=6表示的是满足题目要求的整数5共有6种不同的写法。由于函数的自变量取值为自然数，因此可以将函数表示为：y=f(n)，其中n为自然数。
接下来的问题便是如何求解f(n)？
首先来考虑一个特例，那就是f(5)如何求解。
想象一下假设在我们面前有三堆整数，其中第一堆H1有若干个1，第二堆H2有若干个3，第三堆H3有若干个4。那么如何从这三堆数里面拿走若干个整数使得这些整数之和为5。
由于所有拿走的整数之和相加等于5，因此需要分多次拿。为简化问题的分析，接下来只考虑第一次拿数的情况。
第一种情况：第一次从第一堆H1中拿走一个1，接下来会发生什么。
第二种情况：第一次从第二堆H2中拿走一个3，接下来会发生什么。
第三种情况：第一次从第三堆H3中拿走一个4，接下来会发生什么。
请大家思考第一次拿数，除了上面之外，还有没有其他的情况？
答案显然是没有了，于是接下来便是分析这三种情况的解。
第一种情况
总和为5，第一次从H1中拿了一个1，5-1=4表示接下来还要凑够4。凑够整数4一共有多少种方法呢？答案就是f(4)。此处请大家回忆在开始处定义的函数f(n)的含义。因此第一种情况的解是f(4)。
第二种情况
总和为5，第一次从H2中拿了一个3，5-3=2表示接下来还要凑够2。凑够整数2一共有多少种方法呢？答案就是f(2)。此处请大家回忆在开始处定义的函数f(n)的含义。因此第一种情况的解是f(2)。
第三种情况
总和为5，第一次从H3中拿了一个4，5-4=1表示接下来还要凑够1。凑够整数1一共有多少种方法呢？答案就是f(1)。此处请大家回忆在开始处定义的函数f(n)的含义。因此第一种情况的解是f(1)。
以上完成了三种情况的求解分别是f(4)、f(2)、f(1)，因此要求f(5)的解就是上面三种情况之和即f(5)=f(4)+f(2)+f(1)。
那如何求解f(4)、f(2)、f(1)呢？有了上面的分析，这个问题是不是很简单了。
因此得出一般的情况是：f(n) = f(n-1) + f(n-3) + f(n-4)，而f(n-1)、f(n-3)、f(n-4)又是按照同样的思路进行求解。分析问题的时候采取的是自上而下的思路，但是问题求解的时候，需要采取自下而上的方法，即先必须求得f(1)、f(2)、f(3)、f(4)的值，然后才能继续向后求解f(5)、f(6)···f(n)。
f(1) = 1 (1)
f(2) = 1 (1,1)
f(3) = 2 (3), (1,1,1)
f(4) = 3 (4), (3,1), (1,1,1)
第三步：代码实现。
有了上面的细致分析，接下来就可以快速的写出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 for i in range(5, MAX_N): dp[i] = dp[i - 1] + dp[i - 3] + dp[i - 4] print(dp) |
结语
本文通过一个简单的凑整数案例，介绍了函数的基本思想，并将其应用到解决问题的思路中，帮助大家深入的理解函数。利用动态规划的思路分析问题、解决问题并最终完成了python代码的编写。
