To reach cell , you must have come from either:
Cell - you moved down
Cell - you moved right
So the transition is: dp[$i$][$j$] = dp[$i$-1][$j$] + dp[$i$][$j$-1] The paths from above plus the paths from the left. If either neighbor is out of bounds, treat it as 0. The transition is the core of any DP solution. It defines how the answer for the current state depends on answers for previous states. Getting the transition right is often the hardest and most rewarding part.