"経路" AtCoder Beginner Contest 037 D

経路

解法
解答のpdfがまだなかったため、ACされた方のコードをいくつか読んで参考にさせてもらいました。
深さ優先検索だけだとTLEになってしまったのでdpという配列を作ってメモ化再帰にしました。
あるマスについて上下左右に進めるかをチェックして進める場合はそこからまた上下左右をチェックして……、という再帰になっていて、調べ終わったら配列dpに記録します。
既に探索した場所ならば配列dpに記録してあるので、その値を返します。
入力例1に対応するboardは
0 0 0 0 0...
0 1 4 5 0...
0 2 4 9 0...
0 0 0 0 0...
............
という風にして、端のマスからは進めないようにしてから各マスを出発点としてdfsをしています。

// ABC037D
#include <bits/stdc++.h>
#define REP(i,n) for(int i = 0; i < (int)(n); ++i)
using namespace std;
int board[1002][1002];
long long dp[1002][1002];
long long mod = 1000000007;
int H, W;
 
void shokika(){
    REP(i,1002){
        REP(j,1002){
            board[i][j] = 0;}}
}
 
long long dfs(int i, int j){
    if(dp[i][j]) return dp[i][j];
    long long temp = 1;
    if(board[i][j] < board[i][j+1]) temp += dfs(i,j+1);
    if(board[i][j] < board[i+1][j]) temp += dfs(i+1,j);
    if(board[i][j] < board[i][j-1]) temp += dfs(i,j-1);
    if(board[i][j] < board[i-1][j]) temp += dfs(i-1,j);
    return dp[i][j] = temp % mod;
}
 
int main() {
    int H, W;
    cin >> H >> W;
    shokika();
    for (int i=1; i<=H; i++) {
        for (int j=1; j<=W; j++){
            cin >> board[i][j];}}
 
    long long ans = 0;
    for (int i=1; i<=H; i++) {
        for (int j=1; j<=W; j++){
            ans += dfs(i,j);}}
 
    cout << ans % mod << endl;
    return 0;
}