Dynamic-Programming
动态规划
简介
动态规划问题的一般形式都是求最值，比如求最长递增子序列，最小编辑距离等。
动态规划问题可以穷举结局，然后再求最值，但是都会存在重叠子问题，所以需要备忘录来优化穷举过程，避免重复计算。
动态规划的核心是要写出正确的状态转移方程，也是其中最困难的。
思维框架
明确状态->定义dp数组/函数的含义->明确选择->明确base case
斐波那契数列
递归形式
int fib(int N){
if(N==1 || N == 2) return 1;
return fib(N-1) + fib(N -2);
}
- 当N非常大时里面就会有许多重复计算，导致计算非常低效
递归算法的时间复杂度=子问题的个数乘以解决一个子问题需要的时间
上面子问题个数为$O(2^N)$，解决子问题的时间$O(1)$，所以时间复杂度指数级别，非常慢！
观察就可以发现其中存在许多重叠子问题，可以利用备忘录的递归算法存储。
备忘录的递归算法
int fib(int N) {
if (N < 1) return 0;
// 备忘录全初始化为 0
vector<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];
}
此时时间复杂度就变成了$O(N)*O(1)=O(N)$了。
这种接发和迭代的动态规划差不多了，不过使用的是自顶向下，而动态规划是自底向上。
dp数组的迭代算法（自底向上）
int fib(int N) {
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];
}
由上可以引入状态转移方程
凑零钱
题目
给出k种面值的硬币，面值分别为c1,c2,...ck，每种硬币的数量无限，再给一个总金额amount，问最少需要几枚硬币凑出这个金额，如果不能凑出则返回-1。
要符合最优子结构意思是将问题划分为每个子问题后是相互独立的，如果不独立，则不满足
比如要求amount=11，如果我们知道凑出amount=10的最少硬币数（子问题），则加1就可以得到此问题的答案，两个相互独立是不受牵连的。
一、先确定状态
由于硬币数是无限的，所以唯一的状态就是目标金额amount
二、确定dp函数的定义
即当前的目标金额是n，至少需要dp(n)个硬币凑出该金额
三、确定选择，并选择最优
就是对于每个状态，可以做出什么选择改变当前的状态。对于这个问题，就是当从面额列表coins计划中选择一个硬币，然后目标金额就会相应地减少。
四、最后确定base case
即当目标金额为0，所需硬币数量为0，当小于0，则返回-1
状态转移方程如下
伪代码如下
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
此时给出的还是一般递归形式，其中有很多重复操作，所以可以考虑使用备忘录，在每次dp通过一个数组，保存每次计算的结果。
dp数组的迭代解法
// 非递归，自底向上迭代，带备忘录
int coinChange(vector<int>& coins, int amount){
// 数组大小和初始值都为amount +1
vector<int> dp(amount+1, amount+1);
//base case
dp[0] = 0;
for (int i = 0; i< dp.size(); i++){
//内存for求所有子问题+1的最小值
for(int coin : coins){
if(i - coin < 0) continue;
dp[i] = min(dp[i], dp[i-coin]+1);
}
}
return (dp[amount] == amount+1)? -1 : dp[amount];
}