D - 経路 AtCoder Beginner Contest 037

問題概略
H*Wのマス目がある。好きなマスから好きなだけ自分より大きいマスへ隣に動ける。
移動経路の個数の余りを求めよ。

制約
HW <=1000

解法
自分より大きいところへしか進めないため、閉路はない。
よって経路の数をマスごとにメモできる。
dpに-1を入れておき、移動できるマスの数+1を返すようにすれば動く

public static void solve() throws Exception {
        //longを忘れるなオーバーフローするぞ
        H = ni();
        W = ni();
        long res = 0;
        dp = new long[H][W];
        a = nlt(H, W);
        fill(dp, -1);
        for (int hiq = 0; hiq < H; hiq++) {
            for (int wi = 0; wi < W; wi++) {
                res = modSum(res, dfs(hiq, wi));
            }
        }
        System.out.println(res);
    }

    static long[][] dp;

    public static long dfs(int h, int w) {
        if (dp[h][w] >= 0) return dp[h][w] + 1;
        dp[h][w] = 0;
        for (int i = 0; i < 4; i++) {
            int nh = h + y4[i];
            int nw = w + x4[i];
            if (isOutofIndex(nh, nw, H, W)) continue;
            if (a[h][w] >= a[nh][nw]) continue;
            dp[h][w] = modSum(dp[h][w], dfs(nh, nw));
        }
        return dp[h][w] + 1;
    }