Readme

2189.Number-of-Ways-to-Build-House-of-Cards

本题的直观解读是要将总数n分成若干行之和，每行的牌数是递增的，并且每行的牌数必须是2*k+(k-1)的形式，其中k可以理解为三角形的个数。

我们换个角度来想，假设将行数编号1,2,3,4...就对应三角形的个数，那么每行对应的牌数是2*k+(k-1). 我们的任务其实是将在这些行里面挑选出若干，使得其总数为n。我们可以预料，可供选择的行号不会很多，撑死最多也就是n行（事实上单独的第n行就需要共3n-1张的牌数了）。

我们令dp[i][j]表示前i行里面（挑选若干行）、并且所用牌的总数为j可以得到的方案数。对于第i行而言只有两种选择：1. 我们不选第i行，即不搭建3i-1这种模式，那么dp[i][j] = dp[i-1][j]. 2.我们选择第i行，那么第i行本身占用了3i-1张牌，那么意味着我们关注的就是前i-1行里我们选用j-(3i-1)张牌能搭建多少种合法的方案，所以dp[i][j] = dp[i-1][j-(3i-1)].

于是本题的转移方程就是 dp[i][j] = dp[i-1][j] + dp[i-1][j-(3i-1)]。

初始条件是dp[0][0] = 1，这是所有状态的“种子”。