双色塔问题，读懂屎山代码

现在有红，绿两种颜色的石头，现在我们需要用这两种石头搭建一个塔，塔需要满足如下三个条件：

1．第 1 层应该包含1块石头，第2层应该包含两块，第 i 层需要包含 i 块石头。

2．同一层的石头应该是同一个颜色（红或绿）。

3．塔的层数尽可能多。问在满足上面三个条件的前提下，有多少种不同的建造塔的方案，当塔中任意一个对应位置的石头颜色不同，我们就认为这两个方案不相同。石头可以不用完。

数据范围：红绿颜色石头数量满足 0≤a,b≤2×105 , a+b≥1

给出红石头和绿石头的个数，请输出有多少种叠法

说实话，大家都不喜欢看公式，太难懂，程序员大佬普遍不善表达，我个人也是看了一晚上才大概明白这个题的正确答案是甚么意思，在这里就不贴代码了，只讲一下大体的思路，应该能读的更清晰一些。以及想吐槽一下，希望程序员*********把代码写的清晰易懂一些。

先说一下自己怎么做的：没怎么学过动态规划，考虑的是用递归。定义solution(a,b,i)，a和b分别表示目前红绿石头分别还剩下多少，i表示我目前数到了第i层，这个函数return的就是目前叠到第i层的时候，还剩a个红石头和b个绿石头，会有多少种解决方案。定义这个函数的作用就是不停地往下一层去数，直到进入最深层

写这个问题先定义递归的尽头，当两种颜色的石头的数量都小于需要的石头数量i时，达到尽头了，这种情况下返回1。其实这一步就很完美了，但是不符合条件3，也就是说如果我们这么做的话，会产生一些比较矮的塔。那么我在这里修改为返回 1，i-1两个输出。也就是同时返回个数和这种情况下能够达到的最大层数，以进行后续的比较。

而在else的情况下，分为三种情况：只有红宝石够用，只有绿宝石够用和两种宝石都够用。

只有红宝石够用时，问题转化为solution(a-i,b,i+1),即本层只能使用红宝石

只有绿宝石够用时，问题转化为solution(a,b-i,i+1)，即本层只能使用绿宝石

两种宝石都够用时，问题转化为solution(a-i,b,i+1)和solution(a,b-i,i+1)，但这里不能直接相加，因为要比较深度，两种情况的输出要在比较之后进行处理，再return

而第一层为solution(G,R,1)，此处为函数的入口。

其实这么做基本上很完美了，但是运行速度较慢，提交的时候是不合格的。下面分享大佬的答案。

此题动态规划整理：最重要的是定义数组以及状态转移方程。

如何定义数组？这里大佬使用的是array[i][j]的形式，其含义为堆到第i层时，已经用了j个绿宝石。此处怎么想到的我也不太好讲，但是你要是问为什么不考虑红宝石呢，我会说后面会使用限定条件来让红宝石达到够用的目的。

核心思路仍然为通过前一层来推导当前层，假设前一层已经叠好。这个想法依赖于甚么呢？依赖于我第一层的结果是很好得到的，正常情况下：

array[1][0]=1，我第一层不用绿宝石，那么结果为1

array[1][1]=1，我第一层用绿宝石，那么结果为1

那么假设我已有array[i][*]的全部信息，我如何获得array[i+1][*]?很简单，我在i+1层，要么我就用绿宝石，要么我就不用，当然此处会写判定条件，看看宝石够不够用。