Dynamic Programming Part 2: Basic Problem Solving

We deepen our understanding of dynamic programming by looking at some basic problems, including one that has two parameters in the recurrence.

[mallika]

Notes
31:31 Usually, if the subproblems reoccur, you will get exponential time complexity - the only way you might not, is if the F(n) doesn't depend on F(n-x), but rather on F(n/2)
39:00 Dynamic programming/caching can only be used for deterministic functions, where the value returned for a particular set of arguments is always the same - it cannot depend on input from outside, state should be fully expressed by the function parameters
43:30: You should avoid using global variables in your code. (In python, nested functions have access to the variables defined in the outer function - otherwise, you would pass them around as parameters)
48:08 You could cache (i.e. treat as the key for the map/dict) the 2-d array directly (instead of indices), but you don't want to do that, because looking up the 2-d array would be slow (due to the need to calculate the hash for the array by iterating over its elements, I think, though hashing wasn't explicitly mentioned)
1:05:30 What if there is no safe marker value that could never arise? You could use a map, or you could create another array for the marker, eg a boolean indicator array - it may seem like its getting complicated, but time-complexity wise, it could have better constant factors, avoid map lookups by using array lookups. Another option could be to use "null" constructs, some languages provide this even for primitive datatypes eg nullable integer in C#

[kms]

55:24 we can use 0 when x or y is out of bound, it also works perfectly. isn't it, sir?