请设计一个算法，解决如下问题：给定一个由数字组成的三角形（顶端为根），从顶点出发，每次只能移动到下一行相邻的元素，到达底边结束。路径的得分是该路径经过的所有元素值之和（其中某些位置被标记为发光点，经过则额外加1分）。请找出得分最高的路径，并说明你的算法及复杂度。
考察说明
考察动态规划在三角形路径最优问题中的应用及复杂度分析
回答思路
- 正确理解问题，将“经过最多发光点”转化为带权重的路径得分最大化
- 采用自底向上或自顶向下的动态规划，状态定义为到达某位置的最大得分
- 正确处理相邻移动的约束，避免路径不合法
- 给出时间复杂度和空间复杂度，并说明空间优化方法
- 能清晰阐述状态转移方程及初始化边界
- 对发光点加分的权重设定合理，不遗漏额外加分规则
本题已收录答题指导
本题附完整参考答案与评分标准
登录后可查看结构化答题指导；也可以直接开一场模拟面试，AI 面试官用本题实时追问并给出评分。