題目鏈接：http://noi.openjudge.cn/ch0206/4982/

深搜很好寫(xiě)。

DP：O(n)

d[i] 為走 I 不的方案數(shù)， l[i],r[i],u[i]為第一步走 左，右，上，共走 i 步的方案數(shù)。(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];

?

http://paste.ubuntu.com/23411465/

?

轉(zhuǎn)載于:https://www.cnblogs.com/TreeDream/p/6023846.html

總結(jié)

以上是生活随笔為你收集整理的noi 4982 踩方格的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。