poj2506：Tiling
传送门 题目大意 用2x1与2x2的小方块去填满一个2xn的长条形区域，问有多少种填法。 思路 很标准的dp。假设当前填到第i个位置，那么能继续往后推进的办法只有三种：竖着放一个2x1的方块，或者横着放两个2x1的方块、亦或者直接放一个2x2的方块。即，dp[n]的填法直接取决于dp[n-1]与dp[n-2]。 在n-1时只有一种方法可以填，所以dp[n-1]对dp[n]的贡献就是1*dp[n-1]；在n-2时有三种方法：竖着放俩、横着放俩、放块大的，因为“竖着放俩”的方法与n-1时重叠了，所以dp[n-2]对dp[n]的贡献就是dp[n-2]*2，最终得到转移方程： ```cpp dp[n] = dp[n-1] + dp[n-2] * 2; ``` 样例很善良的提醒了我们这题还是一个大数题目，所以用string来模拟大数加法，避免爆变量。 ```cpp string add(string a, string b) { //维护a长于b if(a.length() < b.length()) swap(a,b); //进位值 int up = 0; //自尾向头计算 for(int i = a.length() - 1, j = b.length() - 1; …