题解分析等闲了就补上(doge),慢慢更新ing
路径计数
比较经典常见的动态规划dp题目了
问题描述
有一个n ×n的网格,有些格子是可以通行的,有些格子是障碍。
一开始你在左上角的位置,你可以每一步往下或者往右走,问有多少种走到右下角的方案。
由于答案很大,输出对1e 9 +7取模的结果。
第一行一个正整数n。
接下来n行,每行n个正整数,1表示可以通行,0表示不能通行。
一个整数,表示答案。
3
1 1 1
1 0 1
1 1 1
#include <bits stdc++.h>
using namespace std;
const int mod = 1e9 + 7;
int main()
{
int a, n;
scanf("%d", &n);
bool is[105][105];
int f[105][105];
for(int i = 1; i <= 1 n; i++) for(int j="1;" <="n;" j++) scanf("%d", &is[i][j]); i="1;" { if(!is[i][j]) f[i][j]="0;" else if(i="=" && 1) continue; } !="1)" - 1]; 1][j]; 1][j] % mod + f[i][j 1] mod) mod; printf("%d", f[n][n]); return 0; }< code></=></bits>
求余运算规则:
设正整数x,y,p,求余符号为%。
对于加法运算: (x + y) % p = (x % p + y % p) % p
对于乘法运算: (x * y) % p = [(x % p) * (y % p)] % p
Original: https://www.cnblogs.com/chr1ce/p/15972800.html
Author: chris599
Title: 路径计数动态规划dp题目
原创文章受到原创版权保护。转载请注明出处:https://www.johngo689.com/583680/
转载文章受原作者版权保护。转载请注明原作者出处!