深入理解动态规划算法 - 凑整数

欢迎点击「算法与编程之美」↑关注我们！

本文首发于微信公众号："算法与编程之美"，欢迎关注，及时了解更多此系列文章。

问题描述

给定正整数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的代码实现部分。

结语

本文通过一个简单的凑整数案例，介绍了函数的基本思想，并将其应用到解决问题的思路中，帮助大家深入的理解函数。利用动态规划的思路分析问题、解决问题并最终完成了python代码的编写。

拓展阅读：

深入理解遗传算法(一)

深入理解遗传算法(二)

从1到100求和学算法思维（一）

从1到100求和学算法思维（二）

从1到100求和学算法思维（三）

从1到100求和学算法思维（四）

从1到100求和学算法思维（五）

从1到100求和学算法思维（六）

where2go 团队

微信号：算法与编程之美

温馨提示：点击页面右下角“写留言”发表评论，期待您的参与！期待您的转发！