动态规划作为算法里面的一大核心，需要牢牢掌握相关技巧。开始学习算法的时候，从递归入手无论是对于思路的转换还是解题的套路掌握都有很大的帮助。然而很多递归的解法都能转化为动态规划的解法，从而大大的缩短计算时间，但是相对的会增加内存的使用（现如今硬件内存啥的都可以用钱解决，但是时间对于用户体验有直接的关系）。
注： 本文章主要以个人经验为主，作为个人笔记以供后序参考使用，有需要的自取。如有表述或理解不准确的地方欢迎指正。
动态规划三大特点：
- 重复子问题
- 存在最优子结构
- 动态转移方程
话不多说，直接上套路
确定
base case， 问题的初始状态确定[状态]，原问题和子问题中会变化的变量
确定[选择]，也就是导致「状态」产生变化的行为
明确
dp函数/数组的定义
关键三要素： 数组、 状态、 选择
子序列套路模板：
- 一维DP数组
**int** n = array.length;
**int**[] dp = **new** **int**[n];
**for** (**int** i = 1; i < n; i++) { **for** (**int** j = 0; j < i; j++) { dp[i] = 最值(dp[i], dp[j] + ...) } }
-
二维DP数组
int n = arr.length; int dp = new dpn;
for (int i = 0; i < n; i++) { for (int j = 1; j < n; j++) { if (arr[i] == arr[j]) dpi = dpi + ... else dpi = 最值(...) } }
个人解题思路
动态规划可以理解为优化递归的一种方式。自顶向下（递归）自底向上（动态规划,也叫自查表）。
写出解法的难点在于会**暴力穷举**，进而写出**动态转移方程**（分段函数）。剩下的无非就是存储的方式:备忘录、DP table、 或更少存储变量。
相关例子
1. 裴波那契数
class fib(object):
*递归方式(自顶向下)的暴力穷举*
def fib1(self, n):
if n == 1 | (n == 2):
return 1
else:
return fib(n-1) + fib(n-2)
* 递推方式(自底向上)的动态规划求解 *
def fib2(self, n):
dp_table = [1, 1]
if n > 1:
for i in range(2, n+1):
dp_table.append(dp_table[i-1] + dp_table[i-2])
return dp_table[n]
*用三个变量替换dp_table，减少内存*
def fib3(self, n):
if n == 0 | (n == 1):
return 1
else:
dp_i = dp_j = 1
for _ in range(2, n+1):
dp_ij = dp_i + dp_j
dp_i = dp_j
dp_j = dp_ij
return dp_ij
裴波那契数最常规的解法就是递归思路， 但是求解的n过大时，做了很多的重复计算，如果将底层的每次计算通过数组的方式进行保存，就能大大的减少计算时间。这样就演变出了动态规划的解法。如果进一步想优化动态规划的解法就要从存储变量上下功夫，这题恰好可以用三个变量代替数组的存储方式。
递归和动态规划解法最主要的差别: 递归自上而下， 动态规划自下而上
如果想刷leetcode， 可参考下面的代码:
def fib3(n):
if n == 0 | (n == 1):
return n
if n > 1:
dp_i = 0
dp_j = 1
for _ in range(1, n):
dp_ij = dp_i + dp_j
dp_i = dp_j
dp_j = dp_ij
return dp_ij
2. 凑硬币
自顶向下的递归（此题不可行，目标金额可能不包括最大值而是由下面的组合而成, 但是理解上可以参考一下
有些特殊的题目可用，比如使用裴波那契数凑硬币）
def coin_change(coins, amount):
# coins：可选面值， amount：目标金额
if amount == 0: return 0
n = 0
while coins:
change_coin = max(coins)
while amount >= change_coin:
amount = amount - change_coin
n = n + 1
coins.remove(change_coin)
if amount > 0:
return -1
else:
return n
自底向上的动态规划解法
class Solution(object):
def coin_change(self, coins, amount):
# coins：可选面值， amount：目标金额
dp_table = (amount+1) * [amount+1]
dp_table[0] = 0
#状态循环，填充dp_table[状态]
for i in range(amount+1):
#可做的选择
for coin in coins:
if i < coin:
continue
dp_table[i] = min(dp_table[i], 1 + dp_table[i-coin])
if dp_table[amount] == amount + 1:
return -1
else:
return dp_table[amount]
另外： 有些题目对于时间和内存都有限制， 需要从递归和动态规划两个思路同时着手。
3. 和为k的最少裴波那契数字组合
这题就是需要同时考虑递归和动态规划。
class Solution(object):
def findMinFibonacciNumbers(self, k):
self.coins = []
self.i = 0
while self.fib(self.i) <= k:
self.coins.append(self.fib(self.i))
self.i += 1
print(self.coins)
return self.coin_change(self.coins, k)
def coin_change(self, coins, amount):
# coins：可选面值， amount：目标金额
if amount == 0: return 0
n = 0
while coins:
change_coin = max(coins)
while amount >= change_coin:
amount = amount - change_coin
n = n + 1
coins.remove(change_coin)
if amount > 0:
return -1
else:
return n
def fib(self, n):
if n == 0 | (n == 1):
return 1
else:
dp_i = dp_j = 1
for _ in range(2, n+1):
dp_ij = dp_i + dp_j
dp_i = dp_j
dp_j = dp_ij
return dp_ij
