The Row Nobody Cleared
Counting paths through an open 3 by 3 grid moving only down and right, with the table rolled down to two rows.
long long dp[2][3] = {};
dp[0][0] = 1;
for (int x = 1; x < 3; x++) dp[0][x] = dp[0][x - 1]; // top row: [1, 1, 1]
for (int y = 1; y < 3; y++) {
int cur = y & 1, prev = cur ^ 1;
for (int x = 0; x < 3; x++) {
dp[cur][x] += dp[prev][x];
if (x) dp[cur][x] += dp[cur][x - 1];
}
}
cout << dp[(3 - 1) & 1][2];
What does this print? (The correct path count is 6.)
Sign in to answer questions and track your progress
Sign In