- 分析题意可尝试动态规划（前层抽屉上锁与未锁对后面抽屉状态无影响），状态描述：
f[i][j][0]：表示前层抽屉锁死个且该抽屉i未锁的方案数。
f[i][j][1]：表示前层抽屉锁死个且该抽屉i上锁的方案数。
状态转移：
（1）考虑f[i][j][0]的上一层抽屉：
转移方程：f[i][j][0]=f[i-1][j][1]+f[i-1][j][0]
边界：f[1][0][0]=1, f[i][0][0]=f[i-1][0][1]+f[i-1][0][0]
（2）类似地，
转移方程：f[i][j][1]=f[i-1][j-1][1]+f[i-1][j][0]
边界：f[1][1][1]=1, f[i][0][1]=f[i-1][0][0]
- 再依照转移方程求解即可，时间复杂度为O(n*m)。
共 1 条回复
看不了图片啊