其实上周只要做8道题目，所以允许我偷个懒，将上周的第9，10道题c v 过来 (qwq)
1.路径计数
有一个n×n的网格，有些格子是可以通行的，有些格子是障碍。
一开始你在左上角的位置，你可以每一步往下或者往右走，问有多少种走到右下角的方案。
由于答案很大，输出对10^9+7取模的结果。
输入格式
第一行一个正整数n。
接下来n行，每行n个正整数，1表示可以通行，0表示不能通行。
输出格式
一个整数，表示答案。
样例输入
3
1 1 1
1 0 1
1 1 1
样例输出
2
数据规模
对于100%的数据，保证2≤n≤100，左上角右下角都是可以通行的。
一开始，我以为这是一道搜素回溯题。但是看到了这里最大的数据规模，100，我就知道这道题不能有dfs做了。那么就只能改变思路。文章来源：https://www.toymoban.com/news/detail-527655.html
我们可以设 f[i] [j] 表示到达点（i，j）的方法数，那么因为只能向下和向右走，所以状态转移方程也很容易了：
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文章来源地址https://www.toymoban.com/news/detail-527655.html
到了这里，关于第二周题解的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
