Answer: Spotify SWE Interview Question 2024 April | Dynamic Programming | on-campus

Solution: Space-Optimized Bottom-Up Dynamic Programming Approach Every cell (i, j) can only be reached from the cell directly above it (i-1, j) or from the cell directly to its left (i, j-1). So the number of unique paths to cell (i, j) is exactly dp[i-1][j] + dp[i][j-1]. Base case: every cell in the first row and first column has exactly 1 path (can only go all-right or all-down respectively). Since we only ever look at the row above, we can ...