算法-数据结构-动态规划

动态规划=回溯+贪心

dp 由来

1. 暴力穷举
2. 带备忘录的递归
3. 非递归的动态规划 即：dp table

dp 解题思路

1. 递归+记忆化-> 递推（倒推）
2. 状态的定义： opt[n],dp[n],fib[n]
3. 状态转移方程：opt[n]=best_of(opt[n-1],opt(n-2))
4. 最优子结构

斐波那契数列

dp(n) 定义：第n层的解法
dp动态转移方程 => dp(n)=n (n<2)
=> dp(n)=dp(n-1)+dp(n-2) (n>=2)

零钱兑换

dp[n] 定义：够成面值n最小的硬笔数量
dp动态转移方程 => dp(n)=n (n=0)
=> dp(n)=min(dp[n-coin[j]]+1])