backtracking, recrusion and DP

[bronze obsidian]

I've been studying datastructures and algorithms for a bit over a month now and I have the final exam on monday, but I still often struggle with coming up with solutions when it comes to backtracking and dp. I feel like I need some help at this point, sometimes it just seems obvious and sometimes I can't get a clue.

So I am wondering if maybe someone could walk me through how they think when solving such problems 🙏

[silent socket]

<@&987246717831381062> please have a look, thanks.

[untold ibex]

it would help if u can give a concrete example

as the details differ heavily per algorithm used etc

[silent socket]

backtracking, recrusion and DP

Changed the title to backtracking, recrusion and DP.

[bronze obsidian]

Absolutely

sec

In this task, we need to find a path from the upper left corner to the lower right corner of a matrix such that we never visit a location that contains an integer we have previously visited. The matrix consists of positive integers under 1000. We can move by stepping right, down, or left (provided that we do not go outside the matrix). Write a method that takes an integer matrix as an input parameter and returns true if a path exists and false if it does not. For full points, you should use an efficient backtracking algorithm to solve the problem (you can also earn 2 points with other solutions). You will find a template in P/HI1029/assignment4. It is okay if the method modifies the matrix during the process. (4 points)

Using for axample the following matrix:
int[][] maze = {{31,32,33,34,37,11,36},
{32,33,35,26,35,36,39},
{31,32,13,32,31,37,37},
{11,39,13,14,15,16,17},
{18,19,33,32,31,32,33},
{16,38,21,22,23,24,25}};

for dp>
An old-fashioned clock has only an hour hand and two buttons. One button advances the clock by 7 hours, and the other advances it by 10 hours. Given that the hand is on a certain time, we must use the two buttons to move the hand to another specified time.

Write a method that takes the start time and target time and returns the minimum number of button presses required to reach the target time. Use a recursive depth-first solution. You can assume that no more than 15 button presses are ever needed. You will find a simple template in P/HI1029/assignment4. (2 points) b) Optimize your solution using dynamic programming.

Sorry for the walls of text, but these are th kind of exam questions we get

So for the first example, I get that I'll use a wrapper and have checks for legal moves along with a boolean array to track the visited indexes but I'm not sure how to implement the helper method.

I have two example solutions as well but I dont think I would come up with them myself

[arctic sundial]

First problem:

You have 3 options left down right at each step. This makes a infinite tree where each node represents your current position in the matrix and each node has 3 children. You simply do a DFS on this tree. But the tree isnt really infinite it must stop somewhere, where:

Your current position is out of bound OR you have met a repeating number OR you have reached the target position.

Second problem:

From the target to the source we go backwards. Each step you can either go back by 7 or 10. This makes a binary tree with each node represents the current distance from the source. Again this tree would be infinite but you stop when you reach the source OR at certain positions you know you can't reach the source no matter what.

And at each step you don't choose both left and right child. You only choose the one with the minimum cost.

The pattern of these problems is: Always start thinking of it as an infinite recursion tree and then you decide where it stops growing and on what condition you can only choose one path, instead of traversing all paths (like in the clock example, each step you don't choose both 10 and 7, but only choose one of them)

• The key is the very first step: how to model all these problems into a tree traversal
• Once you get this first step, the rest should be trivial. Like backtracking states and use memorization to avoid repeated computation.

Just never think of them as backtracking or dp or whatever fancy jargon. They are just recursion trees, unless in some more complicated problems it becomes a graph, not a tree

[bronze obsidian]

Thank you so much for these very well put answers, especially I think it'll make it easier to consider the problems themselves as just recursion trees.

I'll give it a go again after my current "frustration-walk" and report back here how it went ☺️