一.方法介绍

将规模为n的问题，化简为规模为n-1的问题，并且思考从n-1到n的关系是如何的，然后用空间换取时间，用数组来存储这些中间值，(或者用采用递归法)

将问题分解为多个小一点的子问题，然后去找公式关系，也即状态转移方程。
用空间换取时间，用数据记录下中间值，保存子问题的解。对于 dp 数组的定义通常为以 i 结尾的，满足某些条件的子数组数量，
状态转移方程不一定是由n-1过来的，也可能是由前面的状态分割点过来的，比如第279题
当前状态和上一个状态的关系可能不止一种，需要分情况讨论，可以通过举例子来具体分析。比如第91题。
动态规划的题目分为两大类，一种是求最优解类，典型问题是背包问题，另一种就是计数类，比如这里的统计方案数的问题，它们都存在一定的递推性质。前者的递推性质还有一个名字，叫做「最优子结构」 ——即当前问题的最优解取决于子问题的最优解，后者类似，当前问题的方案数取决于子问题的方案数。所以在遇到求方案数的问题时，我们可以往动态规划的方向考虑。
根据状态转移方程，得到滚动数组的思想，来进一步减少存储子结构解的空间，一般是降一个维度的关系

状态存储空间的定义要保证能方便地出现递推式，先定义状态存储空间，再根据这个看能否得出状态转移方程，然后通过此来修正存储空间的定义。
通过写几个i，j，来得出最优解和递归过程之间的关系，然后得到dp的定义
可以通过写几个dp，来推导出状态转移方程，

5.对于0-1背包问题，可以把二维矩阵dp[i][j]画出来，把状态转移的过程描述的更加清楚，是由上一行的哪几个状态得到的

0-1背包问题

给定n个体积为w1,w2,w3,..wn，价值为v1,v2,v3…,vn的物品和容量为C的背包，求这些物品中一个最有价值的子集，使得在满足背包的容量的情况下，包内的总价值最大。并且每个物品只能使用一次。

状态存储变量的定义:
dp[i][j]表示前i件物品体积不超过j的情况下能达到的最大价值。

状态转移方程：
对于动态规划 - 图1 ，如果不考虑物品动态规划 - 图2 放入背包，则有动态规划 - 图3 ；如果将物品动态规划 - 图4 放到背包里，则有动态规划 - 图5 ，如下状态转移方程：
动态规划 - 图6

具体代码实现：
首先物品的外循环，for(i=1,i<=N;i++)
接着是背包容量的内循环j for(j=1;j<=C;j++)
如果容量j大于了物品i的容量w,才能进行状态转移的比较，否则dp[i][j]=dp[i-1][j]，因为一直物品i都放不进去，
上述分析，有了如下的0-1背包问题的代码。

int knapsack(vector<int> weights, vector<int> values, int N, int C) {
        vector<vector<int>> dp(N + 1, vector<int>(C + 1, 0));
        for (int i = 1; i <= N; ++i) {
            int w = weights[i-1], v = values[i-1];
            for (int j = 1; j <= C; ++j) {
                if (j >= w) {
                    dp[i][j] = max(dp[i-1][j], dp[i-1][j-w] + v);
                } else {
                    dp[i][j] = dp[i-1][j];
                } 
            } 
        }
        return dp[N][C];
}

0-1背包的空间极致优化，从O(N*C)优化到O(C)
之所以能这样节省，是因为在计算dp[i][j]时，其两种结果dp[i-1][j]和dp[i-1][j-wi]都和上一行dp[i-1]有关。并且，关键的是，这里的[j]和[j-wi]都是在j被填写之前的值（如果逆序遍历背包容量的话，这就是为了防止结果被覆盖，必须从后向前分别进行计算。）
一开始dp[C]代表的是i=0，没有物品的值，都是初始化为0，
接下来在i=1后，数组dp开始逐渐从后往前被填写值，
在i=2时，数组dp还存储着i=1时的值，相当于分时复用了dp数组。巧妙啊！
下面是具体代码实现

int knapsack(vector<int> weights, vector<int> values, int N, int C) {
    vector<int> dp(C + 1, 0);
    for (int i = 1; i <= N; ++i) {
        int w = weights[i-1], v = values[i-1];
        for (int j = C; j >= C; --j) {
            dp[j] = max(dp[j], dp[j-w] + v);
        } 
    }
    return dp[C];

完全背包问题

给定n个体积为w1,w2,w3,..wn，价值为v1,v2,v3…,vn的物品和容量为C的背包，求这些物品中一个最有价值的子集，使得在满足背包的容量的情况下，包内的总价值最大。并且物品的数量是无限的，可以无限拿取

和0-1背包问题的区别在于，完全背包问题中的所有物体是不限制只有1个的。
因此，解决思路如下
定义动态规划 - 图7 表示在考虑到前动态规划 - 图8 种物品(每种物体不限制次数)和容量为动态规划 - 图9 的背包的情况下，所得到的最大价值。
有这里不再是第动态规划 - 图10 种物品拿和不拿的状态了，而是要列举出第动态规划 - 图11 种物品可以拿多少(取决于当前背包能放的下多少i物品)，因此有：
动态规划 - 图12 ，

如何转换成代码形式？
关键点在哪里？破局点，下面这段代码

//这里的数组都是从下标为1开始，在实际使用时，如果是下标为0开始，则自行减1
if(j>=w[i]){
    for(k=0;k<=j/w[i];++k){
        dp[i][j]=max(dp[i][j], dp[i-1][j-k*w[i]]+k*v[i]); //枚举
    }
}

空间节省？

二.Leetcode题

53.最大子序和-(最简单一维动态规划)

题目链接
状态存储空间：
dp[i]是表示以第i个作为连续子数组的结尾的最大和。

初始值：
dp[0]=0 dp[1]=nums[0]

状态转移方程：
dp[i]=nums[i-1]如果dp[i-1]<0，
否则dp[i]=dp[i-1]+nums[i-1]

最优解：
对dp数组进行求解最大值

存储空间优化：
将一维空间优化成单值空间，用一个变量即可存储，只存储上一个dp即可，
这时需要实时存储一个maxs,来与当前dp比较，保存最大值。

62.不同路径

题目链接
一个机器人位于mxn网格的左上角，机器人试图到达右下角，共有多少种路径?
状态存储的数组定义：dp[i][j]表示(i+1)x(j+1)的格子的可以走的路径。
边界值: dp[0][x]和dp[x][0]的值都为1，因为一旦到达最下边和最右边(只能往右边或者下边走)，只能有一种走法。
状态转移方程：dp[i][j]=dp[i-1][j]+dp[i][j-1],表示对于(i+1)(j+1)的格子可以走的路径而言，等于往右走和往下走到达的状态的和。

63.不同路径||

题目链接

和62题类似，采用动态规划+滚动数组的思想，不过对于滚动数组，dp[0]在matrix[i][0]==1之前，等于1，在之后，就必须等于0，因为此路不通。另一点，在状态转移方程上，dp[j]在matrix[i][j]等于1时，等于0.
```
int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
     vector<int> dp(obstacleGrid[0].size(),0);
     int i,j;
     if (obstacleGrid[0][0]==1||obstacleGrid[obstacleGrid.size()-1][obstacleGrid[0].size()-1]==1)
         return 0;
     dp[0]=1;
     for (i=0;i<obstacleGrid.size();i++) {
         for (j=0;j<obstacleGrid[0].size();j++) {
             if (j==0){
                 if (obstacleGrid[i][0]==1)
                     dp[0]=0;
             }else{
                 dp[j]=(obstacleGrid[i][j]==1)?0:dp[j]+dp[j-1];
             }
         }
     }
     return dp[obstacleGrid[0].size()-1];
 }
```
64.最小路径和
题目链接
grid是一个长m，宽n的二维矩阵
状态存储空间定义：定义dp[i][j]，表示以二维坐标(i,j)的最小路径和，最后的结果则是dp[m-1][n-1]。
初始化：
dp[0][0]=grid[0][0]
dp[0][i]=dp[0][i-1]+grid[0][i] for i from 1 to n-1
dp[i][0]=dp[i-1][0]+grid[i][0] for i from 1 to m-1
状态转移方程：
二重循环i, j
i>=1, j>=1
dp[i][j]=min(dp[i-1][j],dp[i][j-1])+grid[i][j]
70.爬楼梯
题目链接
正在爬楼梯，需要n阶，可以爬1或2个台阶，有多少种不同的方法可以爬到楼顶
n表示爬到第n个阶梯时存在的方法
边界值：f(1)=1, f(2)=2,
取决于你最后登上楼顶是走一步还是两步，f(n)=f(n-1)+f(n-2)

72.编辑距离

题目链接

对于单词A和单词B，实际存在的操作有三个：在A中增加1个字母，在B中增加1个字母，在A中修改1个字母。其他的诸如在A中删除一个字母等等都可以转换为这三种操作。
dp[i][j]定义为对于长度为i的单词A和长度为 j 的单词B，使得其相互转化所需的最小操作数。
要证明dp[i][j]通过dp[i][j-1]，dp[i-1][j]，dp[i-1][j-1]即可完整推导出来，不妨使得每次的操作位置都放在当前A，B单词的末尾的位置，因为只要最后的结果一样，先修改中间字母还是先修改末尾的字母是不影响的，不妨统一成当前情况只修改末尾处，对于中间处可以通过临近的状态进行转换。
dp[i][j]可以是dp[i][j-1]在A的后面增加一个字母，于是操作数即为dp[i][j-1]+1，也可以是dp[i-1][j]在B后面增加一个字母，即为dp[i-1][j]+1，也可以是d[i-1][j-1]，这里又分，若dp[i][j]下的A和B的末尾字母如果相等的话，就不需要修改，dp[i][j]=dp[i-1][j-1]，若dp[i][j]下的A和B的末尾字母如果不相等的话，则需要对A进行修改，则dp[i][j]=dp[i-1][j-1]+1。由于这几种都有可能，所以取最小的。

初始值：dp[0][i]=i，相当于增加 i 个单词，dp[j][0]=j，相当于要增加 j 个单词

int minDistance(string word1, string word2) {
     int len1=word1.size(), len2=word2.size(),i,j;
     vector<vector<int>> dp(len1+1,vector<int>(len2+1));
     for (i=0;i<=len1;i++) {
         for (j=0;j<=len2;j++) {
             if (i==0||j==0)
                 dp[i][j]=(i==0)?j:i;
             else {
                 if (word1[i-1]==word2[j-1])
                     dp[i][j]=min(dp[i][j-1]+1,min(dp[i-1][j]+1,dp[i-1][j-1]));
                 else
                     dp[i][j]=min(dp[i][j-1],min(dp[i-1][j],dp[i-1][j-1]))+1;
             }
         }
     }
     return dp[len1][len2];
 }

91.解码方式

题目链接

状态存储变量的定义：dp[i]为str[0…i]的译码总方式。
状态存储变量的简化：由于dp[i]仅仅和前两项有关，因此可以用两个单变量代替dp[]数组
状态转移方程—分情况讨论，建立最优子结构：

若s[i]==’0’，则若s[i-1]==’1’或’2’时，dp[i]=dp[i-2];否则 return 0 （因为假如最后结尾是10，则这种组合只能被唯一确定，因此dp[i]=dp[i-2]）
若s[i]!=’0’：
则若s[i-1]=’1’，则dp[i]=dp[i-1]+dp[i-2] （s[i-1]和s[i]分开译码，则为dp[i-1],若s[i-1]和s[i]合并译码，则为dp[i-2]，因此状态转移方程为此）
则若s[i-1]=’2’，若1<=s[i]<=6,则dp[i]=dp[i-1]+dp[i-2];（因此可以将这种情况归到上面去）
否则dp[i]=dp[i-1]，（比如末尾是67,则这种情况，只能将6和7分开译码，等价于dp[i-1]）

96.不同的二叉搜索树

题目链接

int numTrees(int n) {
     vector<int> dp(n+1);
     int i,j,k,sum=0;
     for (i=0;i<=n;i++) {
         sum=0;
         if (i==0||i==1){
             dp[i]=1;
         }else {
             for (j=1;j<=i;j++){
                 sum+=dp[i-j]*dp[j-1];
             }
             dp[i]=sum;
         }
     }
     return dp[n];
 }

121.买卖股票的最佳时机-变量存储历史值

题目链接
遍历一遍，保存两个值，第一个值是买入的最小值，第二个值是收益的最大值，往前遍历，一旦遇到比买入的最小值还要小的值，更新买入的值，一旦遇到比买入最小值还要大的值，计算卖出收益，和收益最大值比较，

198.打家劫舍

题目链接
取决于你的当下是由上一个状态怎么过来的
dp理解方式一:
dp[i]表示选择第i个房子进行偷取时，能偷到的最大值
dp[i]=max(dp[i-2]+第i个房子的钱, dp[i-3]+第i个房子的钱)
dp[1]和dp[2]和dp[3]都是确定的，则计算到dp[n]并在计算过程中一直取maxp为最大值即可

dp理解方式二:
对于第 k (k>2) 间房屋，有两个选项：
偷窃第 k 间房屋，那么就不能偷窃第 k-1 间房屋，偷窃总金额为前 k-2 间房屋的最高总金额与第 k 间房屋的金额之和。
不偷窃第 k 间房屋，偷窃总金额为前 k-1 间房屋的最高总金额。
在两个选项中选择偷窃总金额较大的选项，该选项对应的偷窃总金额即为前 k 间房屋能偷窃到的最高总金额。

dp[i]表示前i间房屋能偷窃到的最高总金额，则有如下的状态转移方程:
dp[i]=max(dp[i-2]+nums[i],dp[i-1])
边界条件为 dp[0]=nums[0]， dp[1]=max(nums[0],nums[1])
最终的答案为dp[n-1],其中n是数组的长度

213.打家劫舍||

题目链接

和198相比的区别在于数组的首尾是相邻的，因此，分类讨论，考虑第一个房子而不考虑最后一个房子，下标从[0,n-2]进行dp；不考虑第一个房子，而考虑最后一个房子，下标从[1,n-1]进行dp。然后取两种情况的最大值即可。

279.完全平方数

题目链接
对于分割类型题，动态规划的状态转移方程通常并不依赖相邻的位置，而是依赖于满足分割条件的位置。
我们定义一个一维矩阵 dp，其中 dp[i] 表示数字 i 最少可以由几个完全平方数相加构成。
并且位置 i 只依赖 i-k2 的位置，如 i - 1、i - 4、i - 9 等等，才能满足完全平方分割的条件。
因此 dp[i] 可以取的最小值即为 1 + min(dp[i-1], dp[i-4], dp[i-9] · · · )。

状态转移方程是dp[i]= 1 + min(dp[i-1], dp[i-4], dp[i-9] · · · )。(由于这里的状态转移不再是直接从上一个状态继承下来，而是需要去找状态分割点，列举所有可能的状态分割点，也即存在平方的地方，因此需要for(j=1; j*j<=i; j++)。）

322.零钱兑换-完全背包

由于每种面值是无限的，本质上是完全背包问题，这里先挖一坑，等后续对0-1背包熟悉了，学习完完全背包再来说。

413.等差数列划分

题目链接

状态存储空间的定义：dp[i]表示数组中以下标i结尾的，在(0,i)之间的等差数列的个数。
初始值：dp[0]=dp[1]=0。
状态转移方程：(i>=2)
如果有nums[i]-nums[i-1]==nums[i-1]-nums[i-2]，则dp[i]=dp[i-1]+1，（这里dp[i]是继承了dp[i-1]中等差数列的个数，相当于在前面所有的等差数列后面再拼上nums[i]，这里的+1则是由nums[i], nums[i-1], nums[i-2]这三个数组成的原来dp[i-1]里面没有的新的等差数列）
否则dp[i]不作任何改变。

最后结果：对dp数组进行求和，因为等差数列能任何下标结尾。z

416.分割等和子集

题目链接
状态存储变量：
dp[i][j]表示从数组的[0,i]这个子区间内挑选一些正整数，并且每个数只能用一次，使得这些数的和恰好等于j，这里的dp[i][j]只是表示一种状态，因此可以用bool矩阵

状态转移方程：
在j>=nums[i-1]时：
dp[i][j]=dp[i-1][j] or dp[i-1][j-nums[i]]
这里的含义是对于dp[i][j]而言，想要等于true，要么不选择nums[i]，则在[0,i-1]的区间内必须已经有一部分使得和为j，则dp[i][j]=true; 要么选择nums[i]，则在[0,i-1]区间内必须找到一部分元素，使得其和为j-nums[i]。

在j<=nums[i-1]时：
dp[i][j]=dp[i-1][j] (很重要，不能省略不写，要不然状态传递不下去)

代码:

bool canPartition(vector<int>& nums) {
        int sum=accumulate(nums.begin(),nums.end(),0);
        if(sum%2) return false;
        int target=sum/2,i,j,n=nums.size();
        vector<vector<bool>> dp(n+1,vector<bool>(target+1,false));
        for(i=0;i<=n;i++)
            dp[i][0]=true;
        for(i=1;i<=n;i++) {
            for(j=1;j<=target;j++) {
                if(j>=nums[i-1])
                    dp[i][j]=dp[i-1][j]||dp[i-1][j-nums[i-1]];
                else
                    dp[i][j]=dp[i-1][j];
            }

        }
        return dp[n][target];
    }

空间压缩：
注意这里的内循环是不需要j>=1的，只需要j>=nums[i-1]即可，因为对于j<=nums[i-1]的值，dp[j]=dp[j],是自动保存着之前的值的，这个和上面的未用空间压缩不一样，上面的要手动dp[i][j]=dp[i-1][j]才行。

 bool canPartition(vector<int>& nums) {
        int sum=accumulate(nums.begin(),nums.end(),0);
        if(sum%2) return false;
        int target=sum/2,i,j,n=nums.size();
        vector<bool> dp(target+1,false);
        dp[0]=true;
        for(i=1;i<=n;i++) {
            for(j=target;j>=nums[i-1];j--) {
                    dp[j]=dp[j]||dp[j-nums[i-1]]; 
            }
        }
        return dp[target];


    }

474.一和零-多维0-1背包

多维费用的0-1背包问题，有两个背包大小，0的数量和1的数量。这里不做深入要求

542.01矩阵

题目链接
如果当前位置为0，则最近的0的距离是0
如果当前位置为1，dp[i][j]=min{dp[i][j-1],dp[i-1][j],dp[i+1][j],dp[i-1][j]}+1，
方法一：常规的动态规划
对于上面的状态转移式子，对应于四种移动方法，并且这四种移动方法的先后顺序不能变

只有水平向左移动和竖直向上移动；
只有水平向左移动和竖直向下移动；
只有水平向右移动和竖直向上移动；
只有水平向右移动和竖直向下移动。

用f(i,j)表示位置（i，j）到最近的0的距离。对于第一种移动方式，有：

1143.最长公共子序列

题目链接
状态存储变量：
dp[i][j]表示text1的字符串长度为i和text2的字符串长度为i的最长公共子序列的长度。

初始值：
（可以在循环遍历的时候再进行初始化，不一定非要单独拿出来初始化）
dp[0][j]=0
dp[i][0]=0

状态转移方程：i>0, j>0时
当text1[i-1]==text2[j-1]时，易知dp[i][j]=dp[i-1][j-1]+1 （注意这里的字符串的下标是从0开始的，因此长度为i的字符串的最后一个位置的下标为i-1）
当text1[i-1]!=text2[j-1]时，则dp[i][j]=max(dp[i][j-1], dp[i-1][j])。
这里的解释是增加一个字符，有可能是text1[0:i-1]和text2[0:j]有相等的字符，
这里的dp[i-1][j]是如何赋值的，还有dp[i][j-1]也是如何赋值的？
是一个二重循环，先从外循环是i，内循环是j，所以在计算dp[i][j]时，说明dp[i-1][j]和dp[i][j-1]都是已经计算完了的，并不是自己所理解的i和j都同时++，一层循环就能解决的那个。

119.杨辉三角||

题目链接
这里介绍一种节省空间的滚动数组的方法。
由于杨辉三角当前行第 i 项的计算只与上一行的第 i-1项和第 i 项有关，因此可以倒着计算当前行，这样在计算第 i 项时，第i-1 项仍然是上一行的值。
还有一点，对于每一行的末尾，可以统一成上一行的第 i-1项和第 i 项相加，因为上一行的第 i 项目未被赋值，必然是0，上一行的 i-1 项是1，因此得到该行的末尾是1。（这是由初始化时决定的）

class Solution {
public:
    vector<int> getRow(int rowIndex) {
        vector<int> row(rowIndex + 1);
        row[0] = 1;
        for (int i = 1; i <= rowIndex; ++i) {
            for (int j = i; j > 0; --j) {
                row[j] += row[j - 1];
            }
        }
        return row;
    }
};

22.括号生成

题目链接
采用状态转移的方式很合理，自己一开始也是想着去和上一个状态进行对比寻找，那这样的话，能不能只保存上一个状态的值呢？做个例子，理论和演示上可以，不过在遍历和实现上，不太好找插入的位置。因此，进一步推进，固定当前状态的新增括号（左括号置于最左边），把剩下的 i-1 个括号随机分配到新增括号的相对位置上，相当于得利用不止上一个状态的dp值，还得是前面已求状态的dp值，

若已知前i-1组括号的组合，先探求如何从 i-1 过渡到 i 组括号的组合；
为了避免重复，可以把新增的左括号都放在第一个位置，这个需要探求的，就是新增的右括号和已知的前 i-1 组括号的相对位置（如对于 i=2，有”()()”、”(())”，则对于i=3，这里的”()(())”的一种可能可以视为”()(())”），也即强行规定新括号出现的位置，避免一些重复。这样对于i-1组括号的组合，就分为出现在新括号内和新括号外的情况。
dp[i]表示 i 组括号的所有可能组合，dp[0]={“”}，dp[1]={“()”}
对于dp[i]，根据2的思路，可以变成”(“+p+”)”+q，其中p和q的组括号数相加为i-1,

这里p和q的括号数确定情况下，是去找之前已经求解过的dp的解，因为括号数确定，仍然有不同的情况，因此有遍历

vector<string> generateParenthesis(int n) {
     vector<vector<string>> dp(n+1);
     dp[0]={""};
     dp[1]={"()"};
     int i,j;
     for (i=2;i<=n;i++){
         for (j=0;j<i;j++){
             for (string p:dp[j]){
                 for (string q:dp[i-j-1]){
                     string newstr="("+p+")"+q;
                     dp[i].push_back(newstr);
                 }
             }
         }
     }
     return dp[n];

 }

300.最长递增子序列

题目链接

时间复杂度为O(n^2)的dp方法很好想，dp[i]定义为以nums[i]结尾的最长递增子序列

对于时间复杂度为O(nlong(n))的解法。以下几点

定义一个保存当前最长递增子序列的数组A，对于nums[i]，如果A中没有比nums[i]还大的，则将nums[i]加入到A中，并增加子序列的长度。如果A中有比？？？

787.K站中转内最便宜的航班

题目链接
？？？？？？？？

1769.移动所有球到每个盒子所需的最小操作数

题目链接

dp[i]表示移动到盒子 i 所需的最小操作数，dp[0]很容易求，一次遍历即可。

对于dp[i] (i>=1)，从dp[i-1]到dp[i]的过渡，假设 i 的位置右边有m个1，左边有n个1（包括 i 的位置），则对于位置 i的dp[i]=dp[i-1]-m+n。相当于每个1从右边到i的位置比i-1的位置更进1，从左边到 i 的位置比 i-1 更远1，

vector<int> minOperations(string boxes) {
     int i,j,k,lens=boxes.size(),left,right=0;
     vector<int> ans(lens,0);
     for (i=1;i<lens;i++) {
         if (boxes[i]=='1'){
             ans[0]+=i;
             ++right;
         }
     }
     left=(boxes[0]=='1')? 1:0;
     for (i=1;i<lens;i++) {    
         ans[i]=ans[i-1]-right+left;
         if (boxes[i]=='1'){
             --right;
             ++left;
         }
     }
     return ans;
 }

动态规划

一.方法介绍

0-1背包问题

完全背包问题

二.Leetcode题

53.最大子序和-(最简单一维动态规划)

62.不同路径

63.不同路径||

64.最小路径和

70.爬楼梯

72.编辑距离

91.解码方式

96.不同的二叉搜索树

121.买卖股票的最佳时机-变量存储历史值

198.打家劫舍

213.打家劫舍||

279.完全平方数

322.零钱兑换-完全背包

413.等差数列划分

416.分割等和子集

474.一和零-多维0-1背包

542.01矩阵

1143.最长公共子序列

119.杨辉三角||

22.括号生成

300.最长递增子序列

787.K站中转内最便宜的航班

1769.移动所有球到每个盒子所需的最小操作数