大家还记得汉诺塔和背包吗？递归算法是一道坎，动规算法是另一道坎，我觉得我还没迈过动规算法这道坎，状态转移方程只能靠记忆，自己不会推导。今天先回顾回顾汉诺塔吧，有

大家还记得汉诺塔和背包吗？递归算法是一道坎，动规算法是另一道坎，我觉得我还没迈过动规算法这道坎，状态转移方程只能靠记忆，自己不会推导。今天先回顾回顾汉诺塔吧，有三根编号分别为A、B、C的杆，A杆自下而上、由大到小的顺序放置着n个圆盘，每次只能移动一个圆盘，移动过程中三根杆上都始终保持大盘在下、小盘在上，要如何把A杆上的圆盘全部移到C杆上。

离散傅里叶变换（DiscreteFourierTransform，缩写为DFT），是傅里叶变换在时域和频域上都呈离散的形式，将信号的时域采样变换为其DTFT的频域采样。在形式上，变换两端（时域和频域上）的序列是有限长的，而实际上这两组序列都应当被认为是离散周期信号的主值序列。即使对有限长的离散信号作DFT，也应当将其看作其周期延拓的变换。

扩展资料:傅立叶变换，表示能将满足一定条件的某个函数表示成三角函数（正弦和/或余弦函数）或者它们的积分的线性组合。在不同的研究领域，傅立叶变换具有多种不同的变体形式，如连续傅立叶变换和离散傅立叶变换。最初傅立叶分析是作为热过程的解析分析的工具被提出的。Fouriertransform或TransforméedeFourier有多个中文译名，常见的有“傅里叶变换”、“付立叶变换”、“傅立叶转换”、“傅氏转换”、“傅氏变换”、等等。

FFT全称为快速傅立叶变换。FFT是“FastFourierTransformation”的缩写，即为快速傅氏变换，是离散傅氏变换的快速算法。1、快速傅里叶变换，即利用计算机计算离散傅里叶变换(DFT)的高效、快速计算方法的统称，简称FT。快速傅里叶变换是1965年由J.W.库利和T.W.图基提出的。采用这种算法能使计算机计算离散傅里叶变换所需要的乘法次数大为减少，特别是被变换的抽样点数N越多，FFT算法计算量的节省就越显著。

充分利用DFT计算式中指数因子所具有的对称性质和周期性质，进而求出这些短序列相应的DFT并进行适当组合，达到删除重复计算，减少乘法运算和简化结构的目的。3、计算离散傅里叶变换的快速方法，有按时间抽取的FFT算法和按频率抽取的FFT算法，前者是将时域信号序列按偶奇分排，后者是将频域信号序列按偶奇分排。它们都借助于的两个特点：一是周期性。