DFS with Memoization (Top-Down DP)

DFS with Memoization (Top-Down DP) You are given a search problem with overlapping subproblems (e.g., optimizing or counting over a grid/graph/string/array state space). You are asked to solve it using DFS with memoization to avoid exponential recomputation. Task Define a state representation (e.g., position, index, remaining budget, bitmask of chosen items, etc.). Implement dfs(state) and memoize results in a hash map/dictionary. Return the required output (optimal value or number of ways). Input/Output Inputs depend on the problem (array/matrix/graph, etc.). Output is an int/bool/list depending on the prompt. Constraints Explain an upper bound on #states and the resulting time complexity. Note: The original prompt is missing; the above captures the interview pattern.