Dynamic Programing - broyda/cp-lib GitHub Wiki

Notes on recursion

• Do not try to reason about recursion by "tracing through" the variable values across the recursive calls. This is a futile exercise.
• On usage of global variables

  Dont change a global variable, just read it. or,
  Change a global variable, but do not use the global variable anywhere for any computation, conditional logic etc.

Dynamic Programming on Trees

Do not mix recursion and memoization inside one for loop say within the for loop that invokes the dfs.Instead separate them out because in harder problems, that's useful.

for (int v: adj[u]) {
   if (v != p) {
      dfs(v, u);
      dp[something] = 
   }   
}

// Instead of the above
for (int v: adj[u]) {
   if (v != p) {
      dfs(v, u);
   }   
}
for (int v: adj[u]) {
   if (v != p) {
      dp[something] = 
   }   
}

Printing solutions

One approach (with printing knapsack solutions as an illustrative example) is to:

• First confirm there indeed exists a solution.
• And then run the recurrence a second time (which will be fasiter since values are cached) and then adjust the print statements in those areas of the code where a solution does exist.

Notes on Day 2 Part 4 (DS)

If we pass the vector where we cache the solution as a reference, we need to push back, call recursion (at the end of which it will print the solution) and pop back. This is classical backtracking in action.
Printing all solutions are exponential in nature (because it uses backtracking). Therefore, you will most likely be tested to write ONE particular solution.

If -1 is a legit return value, how do we distinguish between the -1 (the default) and a legit return value of -1?

Keep a separate boolean array and use the check:

 if (done[x]) {
      return dp[x][y];
 } else {
    // Invoke recursive function
 }

Note on overflow

Using 1 + INT_MAX may cause overflow, so use 1 + 19e instead that wont cause an overflow.