n个位置m种花、相邻不同品种的种植方案数
哪些公司问过
答案要点
- 状态:e[i]表示第i位空着、f[i]表示第i位种花,且前i位都合法的方案数
- 转移:e[i]=e[i-1]+f[i-1];f[i]=e[i-1]×m+f[i-1]×(m-1)
- 初值e[1]=1、f[1]=m,答案为e[n]+f[n];n=2时为m²+m+1,可用于自检
- 滚动变量实现,时间O(n)、空间O(1);n极大时用2×2矩阵快速幂做到O(log n)
- 用long long存结果并取模,乘法前先取模防止溢出
易错点
- 只考虑种花的状态,漏掉了位置可以空着
- 前一位为空时也按m-1种转移,导致少算方案
- 不取模或乘法溢出,n较大时结果错误
面试官常见追问
- 如果要求至少种一朵花呢?
- n非常大,比如10^18怎么办?
- 如果每个位置都必须种花呢?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。
相关面试题
- 最长递增子序列(LIS)27 场
- 动态规划的基础与解题流程26 场
- 爬楼梯(青蛙跳台阶)18 场
- 不同路径(网格路径数)17 场
- 买卖股票的最佳时机16 场
- 编辑距离的动态规划解法16 场
- 零钱兑换:最少硬币数与组合数12 场
- 最长公共子序列(LeetCode 1143)11 场
- 矩阵最小路径和(动态规划)10 场
- 斐波那契数列的几种解法8 场