r*********n
发帖数: 4553 | 1 给一个N x M的长方形和1 x 2的砖头（可旋转90度）。问有多少种方法使得这个长方形
刚好被完全覆盖？
如果这个砖头是n x m，这个题又怎么解呢？ | s*******s
发帖数: 1031 | 2 Use DP:
let f(i, j) as the number of approaches. So:
f(i, j) = 0, if i<1 OR j<1 OR i*j<2
= 1, if i==1 and j==2 OR i==2 and j==1
= f(1, j-2)*f(i-1, j) + f(i-1, 2)*f(i, j-2) // use 1*2 to split
+ f(2, j-1)*f(i-2, j) + f(i-2, 1)*f(i, j-1) // use 2*1 to split
【在 r*********n 的大作中提到】
: 给一个N x M的长方形和1 x 2的砖头（可旋转90度）。问有多少种方法使得这个长方形
: 刚好被完全覆盖？
: 如果这个砖头是n x m，这个题又怎么解呢？
| r*********n
发帖数: 4553 | 3
我之前也是这么想的，用两种砖头放在左上角，然后以砖头的两条边作为分割线，把剩
下来的多边形分成两个长方形（每种砖头都有两种分法），然后再recurse。但是仔细
想一下，发现有种情况没有包括进去：有可能有一种覆盖方法使得两条分割线都从砖头
中间通过，也就是说剩下来的多边形并不等价于两个长方形
split
split
【在 s*******s 的大作中提到】
: Use DP:
: let f(i, j) as the number of approaches. So:
: f(i, j) = 0, if i<1 OR j<1 OR i*j<2
: = 1, if i==1 and j==2 OR i==2 and j==1
: = f(1, j-2)*f(i-1, j) + f(i-1, 2)*f(i, j-2) // use 1*2 to split
: + f(2, j-1)*f(i-2, j) + f(i-2, 1)*f(i, j-1) // use 2*1 to split
| r**h
发帖数: 1288 | | g****o
发帖数: 547 | 5 DP+bitmask肯定能做
刚才在想有没有简单的做法，没想出来
DP+bitmask作为面试太难了，但作为不限时的challenge是出现过的
比如 pocketgems这题
http://pocketgems.com/engineering/questions
题目稍稍加了难度， 1x1,1x2,2x1 三种，一条边特别长:2^1024
大家有兴趣的话，私下里对下答案 呵呵
【在 r**h 的大作中提到】
: 这不是那个经典的状态压缩DP嘛
: http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=11
: 我觉得远超过面试题的难度范围了。。
| g****o
发帖数: 547 | | P**l
发帖数: 3722 | 7 这个不大对吧。
n*m % 2 == 1的时候f(n,m) = 0对吧
split
split
【在 s*******s 的大作中提到】
: Use DP:
: let f(i, j) as the number of approaches. So:
: f(i, j) = 0, if i<1 OR j<1 OR i*j<2
: = 1, if i==1 and j==2 OR i==2 and j==1
: = f(1, j-2)*f(i-1, j) + f(i-1, 2)*f(i, j-2) // use 1*2 to split
: + f(2, j-1)*f(i-2, j) + f(i-2, 1)*f(i, j-1) // use 2*1 to split
| r*********n
发帖数: 4553 | 8 谢谢大家
没想到这到题水这么深，这是一家投行的电面题，我当时用第二楼的方法扯了十几分钟
，然后面官说大方向对了。 | r*********n
发帖数: 4553 | 9 能给一个dp + bitmask的tutorial link吗？
thx
【在 g****o 的大作中提到】
: DP+bitmask肯定能做
: 刚才在想有没有简单的做法，没想出来
: DP+bitmask作为面试太难了，但作为不限时的challenge是出现过的
: 比如 pocketgems这题
: http://pocketgems.com/engineering/questions
: 题目稍稍加了难度， 1x1,1x2,2x1 三种，一条边特别长:2^1024
: 大家有兴趣的话，私下里对下答案 呵呵
|
|
