一、动态规划

1、动态规划特点

        a.重叠子问题

        b.状态转移方程

        c.最优子结构

        题型：求最值               核心：穷举

2、解题套路

        a.明确「状态」

        b.明确「选择」

        c.明确 dp 函数/数组的定义

        d.明确 base case

二、01背包问题

        每个物品可以选择至多1次的背包模型

        物品：前i个自然数:{1,2,3,.,i}，每个数可以使用一次

        背包：整数n

        从“背包"视角描述问题本质：你有一个容量为n的背包和体积为1,2,3，,n的物品，每样物品只有一个，有多少种方案能够将背包恰好装满

例子：
        有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。

物品为：

	重量	价值
物品0	1	15
物品1	3	20
物品2	4	30

问背包能背的物品最大价值是多少？

1>确定dp数组

        dp[i][j]-->物品i放入容量为j的背包，得到的最大价值

2>动态转移

        不放物品i：背包容量为j，里面不放物品i的最大价值是dp[i - 1][j]。

        放物品i：背包空出物品i的容量后，背包容量为j - weight[i]，dp[i - 1][j - weight[i]] 为背包容量为j - weight[i]且不放物品i的最大价值，那么dp[i - 1][j - weight[i]] + value[i] （物品i的价值），就是背包放物品i得到的最大价值

3>递归公式

        dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);

4>初始化

5>确定遍历顺序

        可以先遍历背包在遍历物品，也可以先遍历物品在遍历背包

思考过程：

首先对于整个问题：m个物品，背包容量最大为n。

        初步将问题分解为：在已经知道了前m-1个物品的所有最优解的情况下（即无论背包容量多少），再加上第m个物品的情况。

此时有三种情况：

1、第m个的重量超过了背包容量n，不可能放下第m个，所以此时的最优解，就是m-1个物品，背包容量为n的最优解。

2、第m个的重量小于n，可以放但是不放，此时的最优解仍然是m-1个物品，背包容量为n的最优解。

3、第m个的重量小于n，可以放而且真的放了，此时最优解就是第m个物品的价值，加上，m-1个物品时背包容量为（n-第m个物品的重量）的最优解。

根据递推关系发现，构造问题的最优解，不仅需要一个i来标识选择物品的范围，还需要一个j，来求出在0到i选择物品且背包容量为j时的最优解。从而将dp数组确定为dpij

三、一维dp 数组（滚动数组）  

        如果把dp[i - 1]那一层拷贝到dp[i]上，表达式完全可以是：dp[i][j] = max(dp[i][j], dp[i][j - weight[i]] + value[i]);与其把dp[i - 1]这一层拷贝到dp[i]上，不如只用一个一维数组了，只用dp[j]（一维数组，也可以理解是一个滚动数组）。这就是滚动数组的由来，需要满足的条件是上一层可以重复利用，直接拷贝到当前层。

1>dp[j]表示

        容量为j的背包，所背的物品价值可以最大为dp[j]。

2>递推公式

        dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);

3>初始化      

        dp数组在推导的时候一定是取价值最大的数，如果题目给的价值都是正整数那么非0下标都初始化为0就可以了。

4>确定遍历顺序

                只能先遍历物品在遍历背包

                倒序遍历是为了保证物品i只被放入一次！

四、完全背包问题

        每个物品可以选择无限次的背包模型

        物品：体积分别为1,2,3,.,n的n类物品，每类物品无限个

        背包：容量为n的物品

        从“背包"视角描述问题本质：你有一个容量为n的背包和体积为1,2,3,…,n的物品，每类物品有无限个，有多少种方案能够将背包恰好装满

1>dp数组以及下标的含义

         dp[i][j] 表示从下标为[0-i]的物品，每个物品可以取无限次，放进容量为j的背包，价值总和最大是多少。

2>递推公式

        不放物品i：背包容量为j，里面不放物品i的最大价值是dp[i - 1][j]。

        放物品i：背包空出物品i的容量后，背包容量为j - weight[i]，dp[i][j - weight[i]] 为背包容量为j - weight[i]且不放物品i的最大价值，那么dp[i][j - weight[i]] + value[i] （物品i的价值），就是背包放物品i得到的最大价值

递推公式： dp[i][j] = max(dp[i - 1][j], dp[i][j - weight[i]] + value[i]);

（注意，完全背包二维dp数组 和 01背包二维dp数组 递推公式的区别，01背包中是 dp[i - 1][j - weight[i]] + value[i])）

        01背包：

        完全背包：

3>dp数组如何初始化

        关于初始化，一定要和dp数组的定义吻合，否则到递推公式的时候就会越来越乱。

        首先从dp[i][j]的定义出发，如果背包容量j为0的话，即dp[i][0]，无论是选取哪些物品，背包价值总和一定为0。

4>确定遍历顺序（纯完全背包问题）

既可以 先遍历物品再遍历背包：

也可以 先遍历背包再遍历物品：

注意：先先遍历物品再遍历背包求得是组合数；先遍历背包再遍历物品求得是排列数。

装满背包得最大价值是多少，能不能装满背包==>怎么遍历都可以

问装满这个背包有多少种方法得时候，需要去判断求得是组合数还是排列数；

        1>如果求得是组合数(不强调集合中元素得顺序)，需要先先遍历物品再遍历背包；

        2>如果求得是排列数(强调集合中元素得顺序)，需要先遍历背包再遍历物品。