DP lecture

Dynamic programming lecture - how to approach a problem?

DP 1

• Say that this lecture we'll solve Fibonacci, stairs and min-path in a grid. We'll think which method is better to learn: iterative or resursive. Then harder problems in next lectures. Each lecture is some theory and some problems.
• A DP is an algorithmic technique which is usually based on a recurrent formula and one (or some) starting states. A sub-solution of the problem is constructed from previously found ones. DP solutions have a polynomial complexity which assures a much faster running time than other techniques like backtracking, brute-force etc. (that was a quote by Dumitru from TC). Most DP problems are about optimizing (min or max) certain value/quantity or about counting something, e.g. the number of ways to get from one vertex to the other, or the number of ways to write N as a sum of smaller values. We can also use it to check if something is possible and report YES/NO.
  • In case of optimization or YES/NO problems, you should often consider a greedy approach first. It might give you a much easier solution but it's viable only in some problems and the correctness is often hard to prove. Some problems are a mix of two. The example is max-subarray sum (Kadane’s algorithm).
• Wikipedia says that one of the reasons the word "dynamic" was used is that "it sounded impressive".
• Why iterative (bottom-up) over recursion (top-down)? (https://www.quora.com/Are-there-any-good-resources-or-tutorials-for-dynamic-programming-DP-besides-the-TopCoder-tutorial/answer/Michal-Danil%C3%A1k?share=1&srid=3OBi)
  • iteration is much faster than recursion
  • one can easily see time and space complexity of the algorithm
  • source code is short and clean
  • It allows some more complicated techniques in harder problems, like prefix sums and segment trees.
• Sometimes recursion is better
  • Visiting too many states. Given N, you can repeatedly divide it by 2 or 3. Count something? Recursion will get to some states only.
  • When it's hard to figure out the order, e.g. in graphs. For DAG's, you can do topo-sort first.
• Fibonacci (https://leetcode.com/problems/fibonacci-number/). This is similar to problems about "counting ways" but it's easier because we're just given the formula to use.
  • Make a drawing (tree).
  • Mention O(1) space solution.
  • Mention factorial. Say something about overlapping subproblems and explain why DP isn't needed for factorial.
• Stairs: count ways to get from step 1 to N, if you can jump to one of next 2/3 steps (https://leetcode.com/problems/climbing-stairs/).
  • What if we can make at most K jumps? K is given, K <= N.
• Min path from top-left to bottom-right corner in a grid
  • link: https://leetcode.com/problems/minimum-path-sum/
  • counting version: https://leetcode.com/problems/unique-paths/
• What were base cases in those problems?

DP 2

• Given some numbers like {1, 3, 5} or {1, 2, 3}, we need to tell the total number of ways we can form a number 'N' using the sum of the given three numbers, allowing repetitions and different arrangements. https://leetcode.com/problems/combination-sum-iv/
• Coin change
  • the minimum number of coins used (https://leetcode.com/problems/coin-change/)
  • the number of ways (https://leetcode.com/problems/coin-change-2/)
• Forward vs. pull-from-previous dp (TODO: what's the proper name?)

Dp 3 - wines

• A line of N wines, i-th with (the default/starting) price p[i]. You can sell leftmost or rightmost. The j-th sell gives j*p[i] money. Find the optimal order.
• solution I - dp[L][R] is the best score of remaining interval [L, R]. We know which year it is already.
• solution II - dp[L][R] is the best score so far, outside of interval [L, R].
• solution III - dp[L][R] is the best score for interval [L, R] as if it was the whole sequence.

DP 3.2

• A line of N wines, i-th with (the default/starting) price p[i]. You can sell leftmost or rightmost. The j-th sell gives j*p[i] money. Find the optimal order.
  • We can either define dp[L][R] as the best score so far or the best score for the remaining interval [L, R].
  • Think what is important after making some decisions.
  • https://www.quora.com/Are-there-any-good-resources-or-tutorials-for-dynamic-programming-DP-besides-the-TopCoder-tutorial/answer/Michal-Danil%C3%A1k?share=1&srid=3OBi
  • https://www.geeksforgeeks.org/maximum-profit-sale-wines/
• Knapsack
  • A state can be defined as the set of parameters that can uniquely identify a certain position or standing in the given problem. This set of parameters should be as small as possible to reduce state space. For example: In our famous Knapsack problem, we define our state by two parameters index and weight i.e DP[index][weight]. Here DP[index][weight] tells us the maximum profit it can make by taking items from range 0 to index having the capacity of sack to be weight. Therefore, here the parameters index and weight together can uniquely identify a subproblem for the knapsack problem. https://atcoder.jp/contests/dp/tasks/dp_d There will be a nice twist in the next lecture/video, where weights can be huge but values are small.
• Why shortest path (in a graph with positive edges) works and the longest path doesn't. We would have to keep track of all visited vertices so far.
• Recovering the best solution for optimization problems like for min-path grid or wines.
• Store results only for two layers of DP state domain. Easy for Fibonacci, harder for path-grid and very hard for wines.

DP 3.5 (Push vs Pull)

• push=forward, pull=backwards
• PUSH: There is a row of stones. For each stone, you know your range. Compute the number of ways to get from 1 to N.
• PUSH: probability problems

DP 4 (problems)

• Hmm, maybe this should be split into separate videos?
• First six problems from atcoder dp contest.
• bonus problem: https://codeforces.com/problemset/problem/166/E

DP 5 (single video for each problem)

• https://leetcode.com/problems/best-time-to-buy-and-sell-stock/ and continuations