Solve a massive problem by solving smaller versions of it and remembering the answers.
Dynamic Programming (DP) is just recursion with caching. If you need to calculate fib(5), you need fib(4) and fib(3). Without caching, you calculate fib(3) over and over again, taking O(2^n) time. By saving answers in an array (memoisation or tabulation), it drops to O(n).
Let's look at House Robber: You want to rob houses for max money, but you can't rob two adjacent houses. For every house i, the maximum money you can have is the greater of: (1) skipping it and keeping the max from i-1, OR (2) robbing it, adding its value to the max from i-2.
def rob(nums):
if not nums: return 0
if len(nums) == 1: return nums[0]
dp = [0] * len(nums)
dp[0] = nums[0]
dp[1] = max(nums[0], nums[1])
for i in range(2, len(nums)):
# Transition relation
dp[i] = max(dp[i-1], dp[i-2] + nums[i])
return dp[-1]