公司新来80后大叔，入职才十天，直接把公司搁了三年的烂尾项目给盘活了，没过多久，大叔又拉来自己前同事，俩人直接扛起了整个研发部。
程序员老鬼约 4 分钟刚看到个贴子，说公司来个80后大叔，本来行政嫌年纪大直接拒，是技术总监硬顶着要人。结果才入职十天，把搁置三年的烂尾项目抡圆了，软硬件都能上手，后面还把前同事拉来，两个人扛起整个研发部，那群小年轻一边端茶倒水一边心里打鼓，怕自己饭碗不稳。
网友回帖我看了，有的骂公司年龄歧视，有的嘲讽年轻人只会内耗，不会提升自己。怎么说呢，我觉得这事儿最扎心的一点是——职场从来不看你“几几年”，只看你“行不行”。
年轻人怕失业可以理解，但天天围着大叔拍马屁，不如老老实实蹲在旁边学两手真本事。
不用去艳羡那个80后大叔，只要记住一句话：年龄会过期，技术不会；情绪会过期，价值不会。
面试题：多米诺和托米诺平铺
多米诺和托米诺平铺：一道看着像拼乐高的动态规划题 想象一块很长很长的地砖，尺寸是 2 × n，两行、n 列。 手里只有两种砖：
多米诺：2×1 或 1×2 的小长条 托米诺：L 形的，2×2 的正方形缺掉一个格子
要求是：把这块 2×n 的地板铺满，不重叠、不越界，有多少种铺法？n 会比较大，所以一般还会加一句：结果对 1e9+7 取模。
看着就很“组合爆炸”对吧？n=1、2 还能数一数，n=1000 靠手算就有点离谱了，这种就特别适合动态规划上场。
如果硬来： 从左往右，一格一格试：
这里竖着放一个多米诺 或横着放两个多米诺 或者放个托米诺拐一下
每一格都有分支，分支下面还有分支，很快就树炸了。 所以得找“状态”和“递推关系”，把这个爆炸的搜索压扁成一个数组。
常见写法有一个核心思路：把“铺满”和“缺一块”都当成状态。
设：
f[i]：把整块 2×i 的棋盘完全铺满 的方案数g[i]：把 2×i 的棋盘铺到只剩一格空着（某一侧缺一个角） 的方案数
为啥需要 g[i] 这种半截状态？ 因为托米诺是 L 形，经常会导致“这一列没对齐，多出一格”这种尴尬局面，如果不用一个状态记录，写递推会非常绕。
f[i] 怎么转移？
看最后一列是什么样子：
竖着一个多米诺
前面就是一块 2×(i-1) 的完整棋盘 贡献： f[i-1]
横着两个多米诺
会占用 i 和 i-1 两列 前面是 2×(i-2) 的完整棋盘 贡献： f[i-2]
最后一块涉及托米诺这里就要用到 g 了：
想象倒数第二列是“缺一块”的状态 再用一个托米诺把缺的地方补齐，同时带出另一侧的一个格子 左边所有可能缺的情况，都在 g[i-1]里注意托米诺可以朝两边拐，所以是 2 * g[i-1]
综合一下：
f[i] = f[i-1] // 竖着一个多米诺
+ f[i-2] // 两个横着多米诺
+ 2 * g[i-1] // 托米诺相关
g[i] 怎么转移？
g[i] 是“一边多伸出一块”的状态，也看最后一列怎么形成：
从
g[i-1]来：
最后一列用一个竖着的多米诺，把之前那种“缺一块”的形态继续往右拉 贡献： g[i-1]
从 f[i-2] 来：
前面 2×(i-2) 完整 后面用一个托米诺拐出一个“多一格”的状态 贡献： f[i-2]
所以：
g[i] = g[i-1] + f[i-2]
有了两个式子，基本就收工了。
手动算一下前几项：
f[0] = 1：空棋盘算 1 种（啥也不放）f[1] = 1：只能竖着放一块多米诺f[2] = 2：竖竖 横横
g[0]、g[1] 可以先设成 0，第一种“缺角”的合法形态出现在 i = 2：
g[2] = 1：就是一个托米诺挂在 2×2 的角上，只留下一个缺的格子
剩下的直接 for 循环推就完事了。
来段常规写法，用数组存一下，顺便加上取模：
publicclassDominoTrominoTiling{
privatestaticfinalint MOD = 1_000_000_007;
publicintnumTilings(int n){
if (n == 0) return1;
if (n == 1) return1;
if (n == 2) return2;
long[] f = newlong[n + 1]; // 完全铺满
long[] g = newlong[n + 1]; // 缺一格
f[0] = 1;
f[1] = 1;
f[2] = 2;
g[0] = 0;
g[1] = 0;
g[2] = 1;
for (int i = 3; i <= n; i++) {
f[i] = (f[i - 1] + f[i - 2] + 2 * g[i - 1]) % MOD;
g[i] = (g[i - 1] + f[i - 2]) % MOD;
}
return (int) f[n];
}
// 小测试
publicstaticvoidmain(String[] args){
DominoTrominoTiling solver = new DominoTrominoTiling();
for (int n = 1; n <= 10; n++) {
System.out.println("n = " + n + ", ways = " + solver.numTilings(n));
}
}
}
时间复杂度 O(n)，空间 O(n)，如果面试官想扣你空间，还可以把 f[i-1]、f[i-2]、g[i-1] 这几个值用几个变量滚动起来，空间直接压到 O(1)。
这个题有个更简洁的递推：
f[i] = 2 * f[i - 1] + f[i - 3]
它其实就是把上面的 g 消掉推出来的版本，现场推一遍有点公式感，文章里就不展开了，你有兴趣可以自己按代数算一算，会非常有成就感。
差不多就到这儿，你要是用 Java 刷题，把这个板子记住，以后碰到那种“完整状态 + 半残状态”的题，都可以往这个套路上去靠一靠。
-END-
我为大家打造了一份RPA教程，完全免费：songshuhezi.com/rpa.html