动态规划(Dynamic Programming)，简称DP，这个姓名给人的感觉是一种十分巨大上十分复杂的算法，许多同学看到这个姓名或许就会望而生畏，在面试的时分也十分惧怕被问到动态规划的标题。实际上，它并不是不是一种确认的算法，它是一种最优化的办法求解问题的思维或办法。它是由美国数学家贝尔曼(Bellman)在研讨多阶段决议计划进程的优化问题时提出。不过，与之对应的还有一些与时刻无关的静态规划，如：线性规划、非线性规划等。在运筹学中，动态规划是的十分重要的内容，在各个职业范畴都有着广泛的运用。咱们怎么了解动态规划?

假如一个问题的最优解能够经过其子问题的最优解经过推导得到，那么，咱们就能够先求出其子问题的最优解，依据子问题的解得出原问题的最优解。假如子问题有较多的重复呈现，为了削减重复核算，下降时刻复杂度，则能够自底向上从终究子问题向原问题逐渐求解并先将子问题存储起来，在求解大的子问题时能够直接从表中查询子问题的解，这便是动态规划的根本思维。

简略来来了解便是将一个大问题简化成若干子问题，并存入一个表中，再依据数据表中子问题的解求出大问题的解。这种算法看上去是不是很熟悉?其实，动态规划和分治算法相似，咱们也常常将其和分治算法进行比较。它们都需求将其分化成若干子问题并求解子问题。不同的是分治算法是自顶向下求解各子问题，然后兼并子问题的解然后得到原问题的解;而动态规划是将子问题拆解之后，自底向上求解子问题的解并将存储成果存储起来，在求解大的子问题时直接查询子问题的解，算法功率也将大大的进步。

理论描绘过分僵硬和单调，咱们直接来看一个比方。

斐波那契数列

斐波那契数列

斐波那契数列是一个十分奇特的数列，它由意大利数学家莱昂纳-斐波那契提出，其特征是数列某一项的值是前两项的和，也能够称作黄金分割数列。

莱昂纳多·斐波那契

咱们能够用下面的通项公式来表明斐波那契数列。

从斐波那契数列的公式中可知，数列的第n(n>2)项的值f(n)等于f(n)+f(n-1)，假如要求得f(n)值就需求先求得f(n-1)和f(n-2)的值，为了便于剖析，咱们当假定n=6，咱们能够依照下图进行分化，一步步分化成小的值。

斐波那契

看了上面的图，想必咱们脑海中一种想到了程序的完成，咱们能够直接经过递归的办法就能够求出n项的值，程序很简单，如下所示。

intfib(intn)
{
if(n==1||n==2)return1;
returnfib(n-1)+fib(n-2);
}

可是，很明显这种算法是指数时刻复杂度O(2^n)，其复杂度会跟着n的增加成指数增加，当n取到必定大时，将需求很长的时刻，明显这不是一种最优的算法。不过，仔细观察上图的各个分化项，咱们会发现图中有许多重复的子项，这便是上面这种递归算法复杂度较高的原因。那么，还能不能进行优化呢?答案是必定的。

咱们能够经过动态规划的思维来优化上面这个算法，为了防止许多的重复核算，咱们能够从最底层的子问题开端核算，并经过一个表来存储这些子问题的值，当再次遇到这个值就不需求再从头核算。

如下面的程序，咱们从最小的子问题n=1,2开端向上核算，而且界说了一个vector容器用来存储被核算过的子问题的值，下次再核算大问题时直接调用容器里的值即可。

intfib(intn)
{
vector<int>dp(n,0);
dp[0]=dp[1]=1;
for(inti=2;i<n;i++)
{
dp[i]=dp[i-1]+dp[i-2];
}
returndp[n-1];
}

很明显上面的这种算法，大大下降了算法的时刻复杂度，现在的时刻复杂度便是O(n)了。不过，尽管时刻复杂度下降了，这却是献身了空间交换过来的。实际上咱们还能够进一步去优化，从公式上咱们剖析能够看出，要求出某一项的值咱们需求先求出其前两项子问题的值，当咱们自下而上求解子问题的进程中，咱们直接保存接连两项子问题的值即可。

intfib(intn)
{
intdp[2]={1,1};
for(inti=2;i<n;i++)
{
inttmp=dp[0];
dp[0]=dp[1];
dp[1]=dp[1]+tmp;
}
returndp[1];
}

最长上升子序列

严厉意义上来说，上面的斐波那契数列也不完全算是动态规划问题。由于从动态规划的界说上来看，动态规划问题一般满意三个性质：

• 最优化原理：假如原问题的最优解所分化出的子问题的解也是最优的，咱们就称该问题具有最优子结构，原问题的最优解能够由子问题的最优解推导得出;
• 无后效性：某阶段状况一旦确认，这个状况今后决议计划的影响，它只与当时状况有关;
• 有堆叠子问题：子问题或许会在下一阶段决议计划中被重复屡次用到。

依据动态规划问题的这三个性质咱们再看别的一个比方，最长上升子序列(Longest Increasing Subsequence)问题，简称LIS，这是一个十分经典的动态规划问题。

有一个长度为n的数列a0, a1, ..., a(n-1)，求出这个序列中最长的上升子序列的长度。所谓上升子序列指的是关于恣意的i

咱们先将原问题进行分化，顺次拆解成子问题，如下表：

子序列

咱们的代码能够依照下面来完成，其间，程序里咱们用dp数组保存各个子序列以nums[i]结束的最长子序列长度，max存储最长子序列的长度。

intmaxLIS(std::vector<int>&nums)
{
intmax=1;
std::vector<int>dp(nums.size(),1);
for(inti=1;i<nums.size();i++)
{
for(intj=0;j<i;j++)
{
if(nums[i]>nums[j])
{
dp[i]=dp[j]+1;
}
max=std::max(dp[i],max);
}
}
returnmax;
}

经过上面的两个比方，咱们都学废了吗?常见的还有许多问题能够运用动态规划的办法处理，比方，背包问题，硬币找零，最短途径等。动态规划不是一种固定的算法，对应的问题也是多种多样，但咱们只需把握了其根本的思维，就能够轻松的解出相应的问题，咱们赶快去测验一下吧!

本文转载自微信大众号「Will的大食堂」，能够经过以下二维码重视。转载本文请联络Will的大食堂大众号。