每日一题:路径计数

路径计数 - 题目 - Daimayuan Online Judge

f[i][j]表示从左上角走到(i,j)的方案数

状态转移：(i,j)由(i-1,j)和(i,j-1)转移而来

初始状态：得使得f[1][1]为1,所以初始化f[1][0]或者f[0][1]为1(不要都初始化为1),这没有什么含义，只是用于启动,使得f[1][1]=1

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int  N = 110,mod=1e9+7;
int g[N][N];
int f[N][N];
int n;
int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cin >> g[i][j];
       }
    }
    f[1][0] = 1;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (g[i][j]) f[i][j] = (f[i][j-1] + f[i - 1][j]) % mod;
        }
    }
    cout << f[n][n] << endl;
    return 0;
}

也可以直接从f[1][1]开始

AC代码：

#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
#include<vector>
#define int long long
using namespace std;
const int N=110,mod=1e9+7;
int a[N][N];
int f[N][N];
void solve()
{
	int n;
	cin>>n;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			cin>>a[i][j];
		}
	}
	f[1][1]=1;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(i==1&&j==1) continue;
			if(a[i][j]) f[i][j]=(f[i-1][j]+f[i][j-1])%mod;
		}
	}
//	for(int i=1;i<=n;i++){
//		for(int j=1;j<=n;j++) cout<<f[i][j]<<endl;
//	}
	cout<<f[n][n]<<endl;
}
signed main()
{
	solve();
	return 0;
}