1000ms

Difficulty: 8

所属公司 : 京东

时间 :2025年8月2日

算法与标签>动态规划

会员专享

请先登录，开通会员或购买该题目所属题库（京东机考编程题库），可解锁完整内容。

购买题库开通会员

会员专享

请先登录，登录后可使用今日免费解锁；开通会员，或购买该题目所属题库（京东机考编程题库），可解锁完整内容。

购买题库开通会员

题目描述

在一个无限大的平面直角坐标系中，小A 从原点出发，每一步只能向“上”、“左”、“右”三个方向之一移动 1 个单位，且不允许经过相同的点。求小A 恰好走到第 $n$ 步时的合法走法总数。由于结果可能很大，需对 $10^9+7$ 取模输出。

完整思路

状态定义
- 令 $a_n$ 表示恰好走 $n$ 步的合法路径总数。
- 令 $b_n$ 表示恰好走 $n$ 步，且第 $n$ 步是水平移动（“左”或“右”）的路径数。

题目内容

一觉醒来，小 $A$ 发现自己身处一个无限大的平面直角坐标系的原点。坐标系之神告诉他,他可以在这个坐标系内移动,但每一步只能选择上,左,右三个方向之一，并朝着这个方向移动 $1$ 个单位的距离。特别的，坐标系之神要求小 $A$ 不能经过相同的点。

坐标系之神告诉小 $A$ ，只要他能算出走 $n$ 步的合法方案数，就把他放回现实世界。小 $A$ 刚醒来还无法深入思考，想你帮他计算一下结果。