其實(shí)上周只要做8道題目，所以允許我偷個(gè)懶，將上周的第9，10道題c v 過(guò)來(lái) (qwq)
1.路徑計(jì)數(shù)
有一個(gè)n×n的網(wǎng)格，有些格子是可以通行的，有些格子是障礙。
一開(kāi)始你在左上角的位置，你可以每一步往下或者往右走，問(wèn)有多少種走到右下角的方案。
由于答案很大，輸出對(duì)10^9+7取模的結(jié)果。
輸入格式
第一行一個(gè)正整數(shù)n。
接下來(lái)n行，每行n個(gè)正整數(shù)，1表示可以通行，0表示不能通行。
輸出格式
一個(gè)整數(shù)，表示答案。
樣例輸入
3
1 1 1
1 0 1
1 1 1
樣例輸出
2
數(shù)據(jù)規(guī)模
對(duì)于100%的數(shù)據(jù)，保證2≤n≤100，左上角右下角都是可以通行的。
一開(kāi)始，我以為這是一道搜素回溯題。但是看到了這里最大的數(shù)據(jù)規(guī)模，100，我就知道這道題不能有dfs做了。那么就只能改變思路。文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-527655.html
我們可以設(shè) f[i] [j] 表示到達(dá)點(diǎn)（i，j）的方法數(shù)，那么因?yàn)橹荒芟蛳潞拖蛴易撸誀顟B(tài)轉(zhuǎn)移方程也很容易了：
f ( i , j ) = { f ( i ? 1 , j ) + f ( i , j ? 1 ) i ? 1 > 0 , j ? 1 > 0 f ( i ? 1 , j ) j ? 1 ≤ 0 f ( i , j ? 1 ) i ? 1 ≤ 0 f(i,j)= \begin{cases} f(i-1,j)+f(i,j-1) & i-1>0,j-1>0\\ f(i-1,j) & j-1 \leq 0 \\ f(i,j-1) & i-1 \leq 0 \end{cases} f(i,j)=?
?
??f(i?1,j)+f(i,j?1)f(i?1,j)f(i,j?1)?i?1>0,j?1>0j?1≤0i文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-527655.html
到了這里，關(guān)于第二周題解的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
