- dp[0][0]=dp[1][0]=dp[0][1]=dp[1][1] = 1
- for (int i = 0; i < H; i++) {
- for (int j = 0; j < W; j++) {
- //Skip base cases
- if (i < 2 && j < 2) {
- continue;
- }
- //This code ignores array index bounds as the point is to show the skeleton of DP
- dp[i + 1][j + 1] += dp[i][j];
- dp[i + 2][j + 1] += dp[i][j];
- dp[i + 1][j + 2] += dp[i][j];
- }
- }