竹園論壇

標題: d887 - 1.山脈種類(chain) [打印本頁]

作者: domen111 時間: 2014-8-7 20:54
標題: d887 - 1.山脈種類(chain)
本帖最後由 domen111 於 2014-8-7 20:58 編輯

http://zerojudge.tw/ShowProblem?problemid=d887
既然有人問那就發一下解題分享吧!

dp[ i][j]: i代表第幾步，j代表高度，dp[ i][j]代表走到此點的方法數，如圖

稍微思考一下，發現dp[ i][j]=dp[i-1][j-1]+dp[i-1][j+1]，就是把可以走到(i,j)的點的方法數相加。

可以分成兩半處理，用到中間點的方法數相乘就可以了(詳情見程式碼)

AC code: http://ideone.com/MfI3rx

歡迎光臨竹園論壇 (http://forum.tfcis.org/)