共计 5034 个字符，预计需要花费 13 分钟才能阅读完成。
动静布局问题的个别模式就是求最值 。动静布局其实是运筹学的一种最优化办法，只不过在计算机问题上利用比拟多。
求解动静布局的外围问题是穷举 。因为要求最值，须要将所有可行的答案穷举进去，而后在其中找最值。
动静布局的穷举点有点特地，因为这类问题存在 [重叠子问题]，如果通过暴力穷举的话效率会及其低下，所以须要[备忘录] 或者 [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 就是在用空间换工夫。
