本文共 2568 字，大约阅读时间需要 8 分钟。
像这种简单的DP题目一般都有两个特点：1.长得和搜索题很像，甚至就能用搜索做
2.有一个大的吓人的数据
看清这两点，明确了思路，下面开始进入分析阶段：
1.按照题目要求，最终得到的序列的长度为n，和为s，并且后一项是前一项加a或减b，我们不妨将这个操作封装在一起，记作P操作，即P=(a,-b)。
2.设首项为x，可以得到一个等式x+(x+P)+(x+2P)+...+(x+(n-1)P)=s，将这个式子整理一下，就是nx+P+2P+...+(n-1)P=s，即(s-(P+2P+...+(n-1)P))/n=x。
3.由题意，x肯定是一个整数，并且由于每一个P代表一个a或者一个-b，所以a和b的总数为n*(n-1)/2，也就是说只要确定了a的个数，那么b的个数也就确定了。
4.关键问题是对于一个确定的a的个数，方案不只有一种，而且a的个数肯定是由（1,2,3,...,n-1）这其中的若干项组成的，，我们把这些项看作元素，第i个元素的权值为i于是，下面就开始构造递推方程
5.首先，定义一个数组dp[i][j]，表示前i个元素组成和为j的序列的方案数，这里的和j表示的是所有的a的和，很明显当i!=0时dp[i][0]=1,当j!=0时dp[0][j]=0，然后我们要分两种情况讨论
(1)、i>j时，因为每一个元素i权值都是i，所以当元素的个数大于和的时候，第i个元素的权值已经超过了和，所以第i个元素绝对不能使用，即dp[i][j]=dp[i-1][j]。
(2)、i<=j时，第i个元素的权值是小于等于和的，所以可以用，也可以不用，如果不用，那么就是dp[i-1][j]，如果用，就是dp[i-1][j-i]，这个有点类似于01背包，所以
dp[i][j]=dp[i-1][j]+dp[i-1][j-i]。
OK，通过上面的分析，我们得到了递推方程，但还有一个问题，就是空间的问题，题目给出的i的最大值达到1000，相应的j也就是1000^2，我们是不可能开出这么大的数组的，观察递推方程，我们可以看出下一个状态只和前一个状态有关，而且我们实际上只需要最后一个状态即，dp
[j]，于是可以使用滚动数组。
先简单说明一下什么叫滚动数组，因为DP的过程就是一个递推的过程，在推导的过程中，数组中的每一个元素或者是前一个状态，或者是后一个状态，但是，当我们并不需要中间状态得到保留的时候，可以使下一个状态覆盖之前的一个状态，这样就可以极大的压缩空间。
回到本题，我们定义dp[2][MAX*MAX]，也就是说，后面的状态会把前面的状态覆盖掉。
动态规划算法：
简单介绍深搜后重点来了，这题用动态规划（dp）解才是正解。在讲这题之前首先要回顾一下01背包问题中统计方案数的问题。有容量为c的背包要装入体积为1~n的物品，每种物品各一个，求恰好将背包装满的方案数。
我们用二维数组Bo[i][j]来存储背包容量递增，物品按体积1~n的顺序递增时方案数的情况。i表示有体积为0~i的物品各一个，j表示背包的容量为j。首先要初始化当已有的物品体积数量为0，也就是相当于只有一个体积为0的物品时，背包容量j为0的方案数为1个，而容量大于0的方案数全为0。之后来看关键的状态转移方程：
Bo[i][j]=Bo[i-1][j] i>j
Bo[i][j]=Bo[i-1][j]+Bo[i-1][j-i] i<=j
二维数组是从上到下，从左到右进行计算的，每个元素都与之前已经计算过元素相关。第i行j列的元素，如果i>j，也就是新添加的可选物品的体积大于背包的容积，无法放入背包，所以新添加的可选物品不能够增加方案数。如果i<=j，新添加的可选物品的体积小于背包的容积，有可能与其他物品组合装入背包，这时方案数为当没有添加入i体积物品时背包容量为j的方案数 Bo [i-1][j]， 加上当没有添加入i体积物品时但背包容量恰好可以装入i体积物品的方案数 Bo[i][j]=Bo [i-1][j]+ Bo [i-1][j-i]。这样逐行计算即可知道所有情况下的方案数。但是背包问题和本题有何关系呢，似乎毫不相干？
这题的难点就在于如何将本题转化为01背包问题。
设数列首项为t，F(i)={a,-b},第i项加上F(i)为第i+1项。所以第2项可表示为t+F(1)，第2项可表示为t+F(1)+F(2)，第3项可表示为t+F(1)+F(2)+F(3)...........把第一项到第n项累加起来可得表达式n*t + (n-1)F(1) + (n-2)F(2) + ....... +F(n-1) =s。n*t = s - {(n-1)F(1) + (n-2)F(2) + ....... +F(n-1)}。由于F(i)不为a就为-b，设有c个a，F(i)的系数相加共有1+2+......+n-1 = (n-1)*n/2项目，所以共有c-(n-1)*n/2个b。所以令temp = s - c*a + ((n-1)*n/2 - c)*b，当temp%n = = 0时，说明temp == n*t，满足要求。并且，c为1~n-1个数中的若干个数组合相加而得的，每一种组合都是一种方案，到此，我们就可以发现这题已经转化为求01背包问题的方案数了。即从体积为1~n-1的物品中有几种方案能够恰好填满背包。
| i j | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 2 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 |
| 3 | 1 | 1 | 1 | 2 | 1 | 1 | 1 | 0 | 0 | 0 |
还要注意到时间和空间的节省。时间上因为1~i-1体积的物品加起来最多也只能刚好填满i*(i+1)/2容量的背包，所以大于背包容量大于i*(i+1)/2体积的不用计算，固定初始化为0。空间上也不需要开辟上图那么大的空间，用滚动数组只需开辟两行即可，因为(i,j)的值只与i-1行有关,最终结果也只和最后求得的一行有关，所以只需存储当前行与上一行。
转载地址：https://blog.csdn.net/weixin_38960774/article/details/79424850 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！
发表评论
最新留言
关于作者
