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.