01 Matrix on LeetCode: Multi-Source BFS and Two-pass DP Solution

In Multi-source BFS, we start from multiple source nodes simultaneously instead of starting from a single source node, In this case, all the 0 cells act as the initial sources, and we expand outward in all directions. This works efficiently because BFS inherently explores all nodes layer by layer, guaranteeing that the first time we reach a cell, it is via the shortest possible path. Unlike the naive approach of running BFS separately for each 1 cell (which would be too slow), multi-source BFS spreads out from all 0s in parallel. Again, BFS processes each cell exactly once so this solution will run in O(m*n). As of the DP solution, the recursive approach must NOT create cyclic dependencies. When we are computing the distance for a cell, we are making recursive calls to all its neighbors, right?. But if two cells depend on each other, for example, cell A calls cell B, which in turn calls cell A (or another cell that eventually calls A) before A’s value is finalized, you’ll end up in an infinite loop or incorrect results because the dp value for A is still set to –1 when B checks it. In recursive DP, if we do not ensure that all dependent subproblems are solved before the current cell’s computation, the recursion can “chase its tail” or run infinitely and never reach a stable solution.

Dungeon Game on LeetCode : Finding The Right Question To Ask in DP Problems

I have been solving DP problems for last 2 days and guess what, they are really cooool and fun to solve. Previously I didn’t enjoy this much while solving topic-wise problems on Prefix Sum or Sliding Window. Dungeon Game is my first solved bottom-up DP problem. It’s marked as hard, but I believe it is sort of quite medium level problem.

In DP problems, the main part is to find out what to remember as Errichto said. And for that, you have to know the right question to ask.