动态规划YYDS

这题个人感觉用动态规划更加简单。状态设计：f[i][j]表示a[i][j]的方法数。初始状态：f[1][1] = 1（a[1][1] 表示 初始的1种方案）。状态转移：f[i][j]可以从f[i-1][j] 和 f[i][j-1]转移而来，根据题意，这两种状态取最大值。输出：因为没有固定的终点，使用数组ans表示最终的答案，ans和f[i][j]取最大值。
以样例为例(后项数字为方案数）

.1	.2（max(f[1][1],f[0][2])+1	.max(f[1][2],f[0][3])+1
. 2	#0	#0
#0	.0	.0

以上思路数组请开[105][105],不然会越界
上代码！

#include<iostream>
#include<cstring>
using namespace std;
int n,m,f[105][105],ans = 1;
char a[105][105];
int main()
{
    cin>>n>>m;
    for(int i = 1;i<=n;i++)
        for(int j = 1;j<=m;j++)
            cin>>a[i][j];
    memset(f,0,sizeof f);//初始赋值，必须使用<cstring>才行，不然就用万能头文件！
    f[1][1] = 1;//初始状态
    for(int i = 1;i<=n;i++)
        {
            for(int j = 1;j<=m;j++)
                {
                    if(i == 1&&j == 1)
                        continue;
                    if(a[i][j] == '#')
                    {
                        f[i][j] = 0;
                        continue;
                    }
                    if(f[i-1][j] == 0&&f[i][j-1] == 0)//判断：是否能从f[i-1][j]和f[i][j-1]转移而来
                    {
                        f[i][j] = 0;
                        continue;
                    }
                    f[i][j] = max(f[i-1][j]+1,f[i][j-1]+1);//状态转移方程
                    ans = max(f[i][j],ans);//储存最大值
                }
        }
    cout<<ans<<endl;//输出
    return 0;
}

感觉就是一道基本的线性dp,好像没必要用BFS（练习的请无视）
求个点赞，谢谢了