1
$\begingroup$

So the question is

Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path. You can only move down and to the right.

This is a common interview question on software engineering interviews, it is easily solved by implementing a dynamic programming table in order to discern what path is the least costly.

I am now wondering, is there an easy way to solve an alternative problem? Which would be to find the exact sum of a path in an mxn grid.

For instance the input would be a 3x3 matrix and the target sum would be lets say 4. What type of technique should be used in order to find a path that equals exactly 4 to the bottom right corner from the top left corner.

Improve this question
$\endgroup$
  • $\begingroup$ The problem is NP-hard in general (by a reduction from subset-sum) but it admits an easy psedopolynomial-time dynamic programming algorithm. $\endgroup$ – Steven Nov 24 '20 at 13:59
  • $\begingroup$ Backtracking with memoization will do the job. $\endgroup$ – XRFXLP Dec 8 '20 at 9:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.