面试题库 › C++ / 后端 › n个位置m种花、相邻不同品种的种植方案数

n个位置m种花、相邻不同品种的种植方案数

难度 ★★☆在 1 场真实面经中被问到 方向:C++ / 后端考点:动态规划

哪些公司问过

腾讯1

答案要点

  1. 状态:e[i]表示第i位空着、f[i]表示第i位种花,且前i位都合法的方案数
  2. 转移:e[i]=e[i-1]+f[i-1];f[i]=e[i-1]×m+f[i-1]×(m-1)
  3. 初值e[1]=1、f[1]=m,答案为e[n]+f[n];n=2时为m²+m+1,可用于自检
  4. 滚动变量实现,时间O(n)、空间O(1);n极大时用2×2矩阵快速幂做到O(log n)
  5. 用long long存结果并取模,乘法前先取模防止溢出

易错点

面试官常见追问

完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。

相关面试题