动态规划—–>一类思想

动态规划:
    线性动态规划
    区间动态规划
    背包问题
    状态压缩动态规划
    树型动态规划
    插头动态规划
    数位动态规划
    ......
运筹学 决策过程最优化

一般用来求解最优解问题

递归与DP区别:
    递归:将求解的问题分解为若干个同类的子问题，子问题是否相互独立不影响
    DP:将待求解问题分解成若干个子问题，先求解子问题，然后从子问题的解得到原问题的解，并且子问题之间往往不是互相独立的

DP问题两个性质:
    1.最优子结构性质
    2.重叠子问题性质

动态规划:将待求解问题分解成若干个子问题，先求解子问题，
然后从子问题的解得到原问题的解，并且子问题之间往往不是互相独立的

求解DP类型问题:递归

斐波那契数列:
    1.递归实现---->记忆化搜索----->自上而下求解
    2.非递归实现(DP table)---->迭代----->根据1中的记忆化数组，找到数组之中数据的关系----->自下而上求解

DP解题思路:
    1.辨别是不是DP问题
    2.状态数组:
    状态:子问题的状态/解
    找状态数组:
        (1)用参数来描述状态，用一句话描述最终问题状态
        (2)或者搜索----->记忆化优化----->记忆化数组就是状态数组
    3.找状态转移方程:状态数组中状态之间的关系
        (1)站在中间状态的角度考虑i，默认前i-1个状态的值已经知道
        (2)搜索----->记忆化优化----->记忆化记录答案过程，隐含了转移公式
    4.写代码:写法1或写法2

01背包问题: 有N种不同物品和一个容量为C的背包，每种物品有自己的重量w和价值v，，并且每种物品只有一件，可以装下物品的最大价值是多少?

    1.辨题---->DP
    2.状态数组:
        (1)从前n个物品中选择若干个，重量不超过C，价值最大
        dp[n][c] = ans;
        dp[i][j] = x; 从前i个物品中选择若干个，重量不超过j，价值最大为x
        dp[0][j]=0 dp[i][0]=0
        (2)暴力搜索
    3.找状态转移方程:状态数组中状态之间的关系
        (1)站在中间状态的角度考虑i，默认前i-1个状态的值已经知道
        (2)搜索----->记忆化优化----->记忆化记录答案过程，隐含了转移公式
    4.写代码:写法1或写法2