What Is Dynamic Programming?

Hi! I'm Wookje, and today I'm here to explain dynamic programming. The name sounds grand, but the idea is simple. The basic idea of dynamic programming is to reuse values you have already computed (the fancy word for this is memoization) so that the same computation is not repeated again and again.

For example, look at how $F(5)$, the 5th Fibonacci number, is computed.

See how the same function is called many times for nothing? If you compute $F(2)$ and $F(3)$ first and use those stored values when you compute $F(4)$, you avoid the unnecessary calls. Let me put it a bit more rigorously. Mathematically, the Fibonacci sequence can be defined as $F(n) = F(n-1) + F(n-2)$. Writing down such a formula is called setting up a recurrence. Build a formula that fits the conditions of the problem, move it into code as it is, and dynamic programming becomes very easy to implement.

It works with multidimensional arrays too! Suppose you can move only right or down, and you want the number of ways to get from $D[1][1]$ to $D[x][y]$. You do not have to count every case one by one. Let $D[i][j]$ be the accumulated number of ways to reach $(i, j)$. Then the recurrence $D[i][j] = D[i-1][j] + D[i][j-1]$ solves the problem.

See? Dynamic programming is not hard. Now let's solve a problem!

Moving one cell at a time using only the three directions →, ↓, and ↘, count the number of ways to start at the top-left cell $(1, 1)$ and arrive at the bottom-right cell $(n, m)$.

Go!

The first line contains two integers $n$ and $m$ separated by a space. (1 ≤ n, m ≤ 1,000)

Print the number of ways to get from $(1, 1)$ to $(n, m)$. The number can be very large, so print it modulo 1,000,000,007 ($= 10^9 + 7$).