Dynamic Programming for Technical Interviews

Here’s a heads-up to you though, since this article is the first in (maybe, depending on its reception), a multi-part series on DP, this article will focus on setting the groundwork of DP and I’ll dedicate most of this article to explaining how to arrive at the solutions to classical DP problems, and the general pattern of thought that I use when it comes to DP. If you’re already fully confident of why/how the above DP algorithms work correctly, then reading this article may yield little value, and you may be better off waiting for the next article on DP. They’re fairly simple, and I’ll explain them a bit maybe in the next DP article anyway, so here they are –

Given an N x M grid, find the number of different paths one could take if they start at the top-left corner and end at the bottom-right corner and only move either down or right from each cell.

Source: blogarithms.github.io