Dynamic Programming

1. Dynamic programming 👍

This program shows the dynamic programming and find the shortest path in a grid.

2. How it works ? 💯

This works in finding the shortest path in a grid from the TOP-LEFT to BOTTOM-RIGHT.

This loop in the code below find the minimum in three last direction UP, LEFT and UP-LEFT, and after add it to the value of the grid[i, j]

    for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			ll p = numeric_limits<ll>::max();
			if (i - 1 > 0 && j - 1 > 0)p = path[i - 1][j - 1];
			if (i - 1 > 0)p = min(p, path[i - 1][j]);
			if (j - 1 > 0)p = min(p, path[i][j - 1]);
			if (p == numeric_limits<ll>::max())p = 0;

			path[i][j] = p + a[i][j];
		}
    }