Leetcode 174: Dungeon Game

My first attempt, where I tried top down DP, didn’t work. My second attempt used bottom up DP where I start from the last cell (bottom right) and work my way through to the first cell (top left). So at each cell we calculate its DP value by looking at its right and bottom neighbours to determine the minimum exit value we need to satisfy. So the calculated minimum entry value will be min neighbour – dungeon cell value. That calculated min entry value will be our dp cell. After calculating all dp cells our final result will be at cell 0,0 (top left).

This entry was posted in programming and tagged , , . Bookmark the permalink.

Leave a Reply

Your email address will not be published.