The DFT is the correlation of a signal with a bunch of regularly spaced apart single-frequency vectors. The fft is what you get when applying dynamic programmi

The DFT is the correlation of a signal with a bunch of regularly spaced apart single-frequency vectors. The fft is what you get when applying dynamic programming (memoization and recursive subproblem division) to the DFT.