How many ways 记忆化搜索

2024-08-28 07:48

文章标签 搜索记忆 many ways

本文主要是介绍How many ways 记忆化搜索，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

http://acm.hdu.edu.cn/showproblem.php?pid=1978

第一次见到dp记忆化搜索

这题可以分为两种DP方式，一种是当前的这个点可以到达其他点的方法数，二是能到达当前点的方法数。

第一种方法

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<vector>
#include<cmath>
#include<stdlib.h>
#include<iomanip>
#include<list>
#include<deque>
#include<map>
#include <stdio.h>
#include <queue>

#define maxn 10000+5
#define ull unsigned long long
#define ll long long
#define reP(i,n) for(i=1;i<=n;i++)
#define rep(i,n) for(i=0;i<n;i++)
#define cle(a) memset(a,0,sizeof(a))
#define mod 90001
#define PI 3.141592657

const ull inf = 1LL << 61;
const double eps=1e-5;

using namespace std;

bool cmp(int a,int b){
    return a>b;
}
int mp[110][110];
int dp[110][110],n,m;
int dfs(int x,int y)
{
    int s=0;
    if(x==n&&y==m)return 1;
    if(dp[x][y]>=0)return dp[x][y];///记忆化搜索关键
    int p=mp[x][y];
    for(int i=0;i<=p;i++)
        for(int j=0;j<=p;j++)///搜索以下可能
        {
            if((x+i)<=n&&(y+j)<=m&&(i+j)<=p&&(i+j)>0)
            {
                s+=dfs(x+i,y+j);
                s%=10000;
            }
        }
        dp[x][y]=s;///从1,1 到达当前点的方法数
        return s;
}
int sum;
int main()
{
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    int t;
    cin>>t;
    while(t--)
    {
       scanf("%d%d",&n,&m);
       for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        cin>>mp[i][j];
        memset(dp,-1,sizeof(dp));
        sum=dfs(1,1);
        cout<<sum<<endl;
    }
    return 0;
}