>>109372741
dynamic programming, a technique used to efficiently calculate a desired result by breaking the problem down to subproblems and then using those answers to build the next answer in the chain.
It's notoriously difficult to wrap your head around, there's tons of problem variations, and if you don't do it efficiently your code will blow up exponentially in time complexity.
So an easy example is lets say you have a grid of m rows and n columns. You start at the top left (0, 0), your goal is to move to the final cell, and you can only move down or right. How many different paths can you take?
# m = 4, n = 3
# S is start (0, 0), E is end (3, 2)
S X X
X X X
X X X
X X E
Well it takes 1 step to get to 0,0, and if you notice you can only move down or right, that means each cell in the top row only has 1 path, and each cell in the leftmost column also only has one path. so now you have
1 1 1
1 X X
1 X X
1 X E
So how many paths can you take to get to 1, 1? Well you could go from the cell to the left, or the cell above. So the number of paths you could take to get to 1,1 is (leftPaths + upPaths), so 2. In fact you can calculate all results like this. The formula used to calculate this result is called the recurrence relation. So if you have a grid called dp to store your answers, the answer to any row (r) and column (c) is
dp[r][c] = dp[r - 1][c] + dp[r][c - 1]
filled out our solution is
1 1 1
1 2 3
1 3 6
1 4 10
so 10 paths.
https://leetcode.com/problems/unique-paths/description/
have fun going down the (mostly) useless rabbit hole, if you care
