题目链接：
深搜很好写。
DP：O(n)
d[i] 为走 I 不的方案数， l[i],r[i],u[i]为第一步走 左，右，上，共走 i 步的方案数。(u[i]= d[i-1])
d[i] = l[i] + r[i] + u[i]
= l[i-1] + u[i-1] + r[i-1] + u[i-1] + l[i-1] + r[i-1] + u[i-1];
= 2l[i-1] + 2r[i-1] + 3u[i-1];
= 2d[i-1] + d[i-2];
本文共 289 字，大约阅读时间需要 1 分钟。
题目链接：
深搜很好写。
DP：O(n)
d[i] 为走 I 不的方案数， l[i],r[i],u[i]为第一步走 左，右，上，共走 i 步的方案数。(u[i]= d[i-1])
d[i] = l[i] + r[i] + u[i]
= l[i-1] + u[i-1] + r[i-1] + u[i-1] + l[i-1] + r[i-1] + u[i-1];
= 2l[i-1] + 2r[i-1] + 3u[i-1];
= 2d[i-1] + d[i-2];
转载于:https://www.cnblogs.com/TreeDream/p/6023846.html