动态规划先导

动态规划问题的一般形式就是求最值。动态规划其实是运筹学的一种最优化方法，只不过在计算机问题上应用比较多。
求解动态规划的核心问题是穷举。因为要求最值，需要将所有可行的答案穷举出来，然后在其中找最值。
动态规划的穷举点有点特别，因为这类问题存在[重叠子问题]，如果通过暴力穷举的话效率会及其低下，所以需要[备忘录]或者[DP table]来优化穷举的过程，避免不必要的计算。
而且，动态规划问题一定具有[最优子结构],才能通过子问题的最值得到原问题的最值。
另外，虽然动态规划的核心思想就是穷举求值，但是问题可以千变万化，穷举所有的可行解并不是一件很容易的事，只有列出正确的[状态转移方程]，才能正确地穷举。
上面提到的重叠子问题、最优子结构、状态转移方程就是动态规划的三要素。在实际的算法问题中，写出状态转移方程是最困难的，这也是动态规划问题的难点和痛点。
明确 base case->明确[状态]->明确[选择]->定义dp数组/函数的含义。
最后形成了下面这个框架

//初始化base case
dp[0][0][...]=base
//进行状态转移
for 状态1 in 状态1的所有取值
  for 状态2 in 状态2的所有取值
    for...
      dp[状态1][状态2][...]=求最值(选择1，选择2...)

一、斐波那契数列
东哥讲得很有道理，简单的例子去参透本质，每种题型的细节需要大量的练习。
1.暴力递归
int fib(int N){
if(N==1||N==2){
return 1;
}
return fib(N-1)+fib(N-2);
}
看看算法的时间复杂度，子问题的个数就是递归树中所有节点的总数。显然二叉树的节点总数为指数级别，所以子问题个数为O(2^n)。
观察递归树，很明显发现了算法低效的原因:存在大量重复计算，比如f(18)被计算了两次...
重叠子问题就出现了。
2.带备忘录的递归解法
明确了问题，其实就是把问题解决了一半。既然耗时的原因是重复计算，那么我们可以造一个[备忘录]，每次算出某个子问题的答案后先不着急返回，先记到[备忘录]中；每次遇到一个子问题先去[备忘录]里查一查，如果发现之前已经解决过这个问题了，直接把答案拿出来用，不要再耗时去计算了。

int fib(int N){
 if(N<1) return 0;
 //备忘录全初始化为0
 vecotor<int> memo(N+1,0);
 //进行备忘录的递归
 return helper(memo,N);
}

int helper(vector<int >& memo,int n){
//base case
if(n==1||n==2){
return 1;
}
//已经计算过
if(memo[n]!=0){
return memo[n];
}
memo[n]=helper(memo,n-1)+helper(memo,n-2);
return memo[n];
}

实际上，带[备忘录]的递归算法，把一棵存在巨量冗余的递归树通过[剪枝],改造成了一幅不存在冗余的递归图，极大地减少了子问题(即递归图中节点)的个数。

递归算法的时间复杂度计算方式就是子问题个数乘以解决一个子问题需要的时间。
3.dp数组的迭代解法
有了上一步[备忘录] 的启发，我们可以把这个[备忘录]独立出来称为一张表，这叫做DP table吧，在这张表上完成[自底向上]的推算岂不美哉

int fib(int N){
if(N<1){
return 0;
}
if(N==1|| N==2){
return 1;
}
vector<int> dp(N+1,0);
//base case
dp[1]=dp[2]=1;
for(int i=3;i<=N;i++){
dp[i]=dp[i-1]+dp[i-2];
}
return dp[N];
}

我们可以发现，和上面的剪枝之后的结果很像，只不过就是递归的方式不同而已
所以这么看来，备忘录和DP table解法其实是差不多的，效率也基本相同。

[状态转移方程]其实就是为了听起来高端。你把f(n)想做一个状态n，这个状态n是由n-1和状态n-2相加转移而来，这就叫做状态转移，仅此而已。
上面几种解法中都是围绕状态转移方程列出不同的表达式，例如return f(n-1)+f(n-2)，dp[i]=dp[i-1]+dp[i-2]。可见状态转移方程的重要性，它是解决问题的核心。而且很容易发现，其实状态转移方程直接代表着暴力解法。
动态规划问题最要命的是写出暴力解，即状态转移方程，当我们写出暴力解之后，优化方法无非是用备忘录或者DP table，再无奥妙可言。
斐波那契数列问题的小技巧，当前状态只和前两个状态有关，所以我们可以使用两个变量来存储之前的两个状态。

int fib(int n){
if(n<1) return 0;
if(n==2||n==1){
return 1;
}
int prev=1,curr=1;
for(int i=3;i<=n;i++){
int sum=prev+curr;
prev=curr;
curr=sum;
}
return curr;
}

上面的小技巧叫做状态压缩，之前我们也有使用过这些技巧，只不过没有理论化而已。
二、凑零钱问题
先看下题目:给你k种面值的硬币，面值分别为c1,c2...ck，每种硬币的数量无限，再给一个总金额amount,问你最少需要几枚硬币凑出这个金额，如果不能凑出，算法返回-1。

//coins中是可选硬币面值，amount是目标金额
int coinChange(int[] coins,int amount);

1.暴力递归
首先，这个问题是动态规划问题，因为它具有[最优子结构]。要符合[最优子结构]，子问题间必须要互相独立。
东哥举的例子就是，考试中每门成绩都是独立的。你的问题考出最高分，那么子问题就是把语文考到最高，数学考到最高...为了每门课考到最高，你要把每门课的选择题分数拿到最高，填空题分数拿到最高...当然，最终就是你每门课都是满分，这就是最高的总成绩。
得到了正确的结果:最高的成绩就是总分。因为这个过程符合最优子结构，"每门科目考到最高"这些子问题是相互独立，互不干扰的。
但是，如果加一个条件:"你的语文成绩和数学成绩会互相制约，数学分数高，语文分数就会降低，反之亦然。"如果再按照刚才的思路就会得到错误的结果。因为子问题并不独立，语文数学乘积无法同时最优，所以最优子结构被破坏。
回到凑零钱问题，为什么说它是符合最优子结构呢？比如你想求amount=11时的最少硬币数(原问题),如果你知道凑出amount=10的最少硬币数(子问题),你只需要把子问题的答案加一就是原问题的答案。因为硬币的数量是没有限制的，所以子问题之间是相互独立的。
既然知道了这个是动态规划问题，就要思考如何列出正确的状态转移方程？
1.确定base case,这个很简单，显然目标金额amount为0时算法返回0，因为不需要任何硬币就已经凑出目标金额了。
2.确定[状态]，也就是原问题和子问题中会变化的量。由于硬币数量无限，硬币的金额也是题目给定的，只有目标金额会不断地向base case靠近，所以唯一的[状态]就是目标金额amount。
3.确定选择，也就是导致[状态]产生变化的行为。目标金额为什么变化呢，因为你在选择硬币，你每选择一枚硬币，就相当于减少了目标金额。所以说所有硬币的面值就是你的[选择]。
4.明确dp函数/数组的定义。我们这里讲的是自顶向下的解法，所以会有一个递归的dp函数，一般来说函数的参宿就是状态转移中会变化的量，也就是说上面说到的[状态]；函数的返回值就是求我们计算的量。就本题来说，状态只有一个，即[目标金额],题目要求我们计算凑出金额所需的最少硬币数量。所以我们可以这样定义dp函数:
dp(n)的定义:输入一个目标金额n，返回凑出目标金额n的最少硬币数量。
伪代码

def coinChange(coins:List[int],amount:int):

#定义:要凑出金额n,至少要dp(n)个硬币
def dp(n):
        #做选择，选择需要硬币数量最少的那个结果
        for coin in coins:
           res=min(res,1+dp(n-coin));
        return res;
 
#题目要求的最终结果是dp(amount)
return dp(amount);

e即可得到最终的答案。显然目标为0时，所需硬币数量是0；当目标金额小于0时，无解，返回-1；

def coinChange(coins:List[int],amount:int):

def dp(n):
#base case
if n==0: return 0;
if n<0:return 1;
#求最小值，所以初始化为正无穷
res=float('INF');
for coin in coins:
subproblem=dp(n-coin);
#子问题无解，跳过
if subproblem==-1:continue;
res=min(res,1+subproblem);

return res if res!=float('INF') else -1;

return dp(amount);

再给我们的伪码加上base case

def coinChange(coins:List[int],amount:int);

def dp(n):
#base case
if n==0:return 0;
if n<0:return -1;
#求最小值，所以初始化为正无穷
res=float('INF')
for coin in coins:
subproblem=dp(n-coin);
#子问题无解，跳过
if subproblem==-1:continue;
res=min(res,1+subproblem);

return res if res !=floa('INF') else -1;
return dp(amount);

至此，状态转移方程已经完成了，以上算法已经是暴力解法了

至此，这个问题其实就解决了，只不过需要消除一下重叠子问题，比如amount=11,coins={1,2,5}时画出递归树看看：

我们来看一下时间复杂度，总数为递归树节点个数，是O(n^k)，总之是指数级别的。每个子问题中含有一个for循环，复杂度为O(k)。所以总时间复杂度为O(k*n^k)，指数级别。
2.带备忘录的递归

def coinChange(coins:List[int],amount:int):
#备忘录
memo=dict();
def dp(n):
#查备忘录,避免重复计算
if n in memo:return memo[n]
#base case
if n==0:return 0;
if n<0:return -1;
res=float('INF')
for coin in coins:
subproblem=dp(n-coin)
if(subproblem==-1):continue;
res=min(res,1+subproblem);

#记入备忘录
memo[n]=res if res=float('INF') else -1;
return memo[n];

return dp(amount);

3.dp数组的迭代解法
当然，我们也可以自底向上使用dp table来消除重叠子问题，关于状态和base case与之前没有区别,dp数组的定义和刚才dp函数类似，也是把[状态]也就是目标金额作为变量。不过dp函数体现在函数参数，而dp数组体现在数组索引:
dp数组的定义:当目标金额为i时，至少需要dp[i]枚硬币凑出。

int coinChange(vector<int>& coins,int amount){
//数组大小为amount+1,初始值为amount+1
vector<int> dp(amount+1，amount+1);
//base case
dp[0]=0;
//外层for循环在遍历所有状态的所有取值
for(int i=0;i<dp.size();i++){
//内层for循环在求所有选择的最小值
for(int coin:coins){
//子问题无解，跳过
if(i-coin<0){
continue;
}
dp[i]=min(dp[i],1+dp[i-coin]);
}
}
return (dp[amount]==amount+1)?-1:dp[amount];
}

ps:这里的amount+1相当于初始化为正无穷
总结
1.先想出如何穷举
2.再想办法优化穷举
动态规划之所以难，主要是因为一是穷举需要递归实现，二是有的问题本身的解空间复杂，不那么容易穷举完整。
备忘录、DP Table就是在用空间换时间。