首页 > 代码库 > 很好的矩阵覆盖问题
很好的矩阵覆盖问题
参考这篇文章:
http://www.cnblogs.com/CheeseZH/p/5112946.html
题目描述
我们可以用2*1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2*1的小矩形无重叠地覆盖一个2*n的大矩形,总共有多少种方法?
class Solution { public: int rectCover(int n) { if (n == 1 || n == 2) return n; int a = 1, b = 1; while (n-- >= 2) { a = a + b; b = a - b; } return a; } };
开始看,很难懂是吧,我也看了好一会儿。
把 b = a - b 用上一个式子a = a + b代入,得到,其实 b = a + b - b = a,其实就是b存储了上一个a。
这样就能够看出来,a和b分别存储了上一个结果和上上一个结果。再结合DP的思想,
最终的结果,其实就是竖过来放一个的结果(对应上一个结果)+横过来放两个的结果(对应上上一个结果)。
很巧妙是吧。
很好的矩阵覆盖问题
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。