算法笔记——动态规划

算法笔记——动态规划

动态规划是一个非常灵活的算法，动态规划本身不难，无非就是一个状态转移的过程，难点就在于我们该如何去定义“状态”，而这就需要我们多做题来积累经验，这也是初学者遇到动态规划往往无从下手的原因。

动态规划的核心在于状态和状态转移方程，状态具体该如何去定义，需要大家多做题来体会，下面主要是记录一下动态规划的一般解题思路。

以122. 买卖股票的最佳时机 II为例 给定一个数组 prices ，其中 prices[i] 表示股票第 i 天的价格。 在每一天，你可能会决定购买和/或出售股票。你在任何时候最多只能持有一股股票。你也可以购买它，然后在同一天出售。 返回你能获得的最大利润 。

1.将原问题分解为若干子问题

这一步是为后续的状态定义做一个铺垫，注意分解的子问题一定要是连续的并且可以递推求得原问题的解，且分解的子问题一定要保证不能遗漏（有些情况下可以重复，比如求最大值，有些情况下不能重复，比如求序列和——重复的话就会有元素被用了两次） 问题中是要求我们最终所能获得的最大利润，我们可以将其分解为截止到第一天所能获得的最大利润、截止到第二天所能所能获得的最大利润…截止到最后一天所能获得的最大利润，这样我们就将原来的问题分解为一系列的子问题

2.根据子问题定义状态

根据第一步分解得到的子问题，我们可以根据其进行状态的定义了，状态其实就是对子问题的一种表示，状态的值就是我们所要求的解 我们假设截止到第i天所能获得的最大利润为w，问题中还有一句话你在任何时候最多只能持有一股股票，由此我们可以用一个二维数组dp[][]来表示状态，第一维表示是第几天，第二维则表示你当前是否持有股票，我们可以用0表示没有股票，1表示有股票。 综上，状态定义为：dp[i][0]->截止到第i天没有股票所能获得的最大利润；dp[i][1]->截止到第i天有股票所能获得的最大利润

3.确定边界条件

所谓边界条件就是状态转移方程的初始条件或终止条件 本问题中边界条件就是第1天的状态，第一天没有股票的话就是没有买也没有卖股票所获利润为dp[1][0]=0，第1天有股票的话就是在第一天买了一股股票此时因为没有卖出所以利润为dp[1][1]=-prices[1]

4.确定状态转移方程

状态转移方程就是在确定得到当前状态的方法，即如何从一个已经求出的状态得到当前的状态，并最终递推得到最终值，状态转移方程是根据状态来定的。 本题中第i天的状态为dp[i][0]和dp[i][1]，我们要找到从第i天到第i+1天的状态转移方程，注意题目中在每一天，你可能会决定购买和/或出售股票，我们在每一天可能发生的动作有购买/出售和不做任何操作三种 首先考虑dp[i+1][0]，即第i+1天没有股票的状态，可能的状态转移方程有第i天没有股票，第i+1天不做任何操作；第i天有股票，第i+1天卖出了股票，最大的利润就是这两种转移方程的最大值，表示成代码为：dp[i+1][0]=max(dp[i][0],dp[i-1][1]+prices[i+1]) 然后考虑dp[i+1][1]，第第i+1天有股票的状态，可能的状态转移方程有第i天没有股票，第i+1天买入了股票；第i天有股票，第i+1天不做任何操作最大的利润就是这两种转移方程的最大值，表示成代码为：dp[i+1][1]=max(dp[i][0]-prices[i+1],dp[i][1])

5.返回最终结果

在状态转移方程确定后就可以按顺序计算出最终结果了，这里一定要注意状态转移方程执行的顺序，因为这是一个递推的过程，所以必须保证当前方程用到的上一个状态已经得到了。 本题中，执行顺序就是从第1天开始，依次求到最后一天，然后返回从第一天截止到最后一天没有股票的最大利润即可（注意这里最后一天没有股票的最大利润一定是大于有股票的）

完整代码

    int maxProfit(vector& prices) {
        int n = prices.size();
        int dp[n][2];
        dp[0][0] = 0, dp[0][1] = -prices[0];
        for (int i = 1; i i为考虑前i个物品，j为某种限制，这里是物体体积
 
集合：所有只考虑前i个物品，且总体积不超过j的选法的集合 属性：最大价值
 
2.状态计算：(化整为零) 找最后一个不同点，选不选第i个物品，由此可以将状态表示的集合划分为所有不选第i个物品的方案和所有选第i个物品的方案->满足不重复不遗漏
 
求f[i][j]的最大值只需要分别求选/不选第i个物品的两个集合的最大价值，然后取其中较大的即可。
 
不选第i个物品的最大值：f[i-1][j]
 
选择第i个物品的最大值：分成变化和不变的部分，其中不变的部分即一定要选第i个物品价值为wi，变化的部分为前i-1个物品的最大值f[i-1][j-vi],两者相加为f[i-1][j-vi]+wi
 
Ps:实际情况中还需要特判一下，比如第二种情况当j> n >> v;
    for (int i = 1; i > V[i] >> W[i];
    for (int i = 1; i > v;
    for (int i = 1; i > V[i] >> W[i];
    for (int i = 1; i = V[i]; j--)
            f[j] = max(f[j], f[j - V[i]] + W[i]);
    cout  n >> v;
    for (int i = 1; i > V[i] >> W[i];
    for (int i = 1; i > v;
    for (int i = 1; i > V[i] >> W[i];
    for (int i = 1; i = 1; i--)
    {
        for (int j = i+1; j