动态规划，是利用历史记录来避免重复计算的一种算法，是求解决策过程最优化的过程。一般用一维数组/二维数组来保存历史记录。
（将原问题拆解成若干子问题，同时保存子问题的答案，使每个子问题只求解一次，最终获得原问题的答案。）
一般动态规划有三个步骤：
1.定义数组元素的含义，一般求什么就定义成什么；
2.找出数组元素之间的关系式，类似归纳法；
3.找出初始值；
动态规划三要素:
1.最优子结构：原问题的最优解所包含的子问题的解也是最优的，通过子问题的最值得到原问题的最值。
2.存在重叠子问题：子问题间不独立（这是动态规划区别于分治的最大不同）；如果暴力穷举的话效率会极其低下，所以需要「备忘录」或者「DP table」来优化穷举过程，避免不必要的计算。
3.无后效性：即后续的结果不会影响当前结果。
状态转移方程：一般思考过程，明确「状态」 -> 定义 dp 数组/函数的含义 -> 明确「选择」-> 明确 base case。方程本质是数学的递推式。
解题方法
DP数组的递推计算过程需要注意两点：
1、遍历的过程中，所需的状态必须是已经计算出来的。
2、遍历的终点必须是存储结果的那个位置
主要就是看 base case 和最终结果的存储位置。
例题：
斐波那契类型：
Leetcode——198.打家劫舍
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
示例 1：
输入：[1,2,3,1]
输出：4
解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
偷窃到的最高金额 = 1 + 3 = 4 。
示例 2：
输入：[2,7,9,3,1]
输出：12
解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
偷窃到的最高金额 = 2 + 9 + 1 = 12 。
在第 i 号房子之前可偷窃的最高金额由两种情况确定：
1.第 i-2 号房子前可偷窃的最高金额加上第 i 号房子的存放金额；
2.第 i-1 号房子前可偷窃的最高金额。
两种情况取较大者即可。
转移方程为： dp[i] = max(dp[i-2] + nums[i], dp[i-1])
由转移方程可知，dp 数组的值取决于前两个 dp 数组的值，因此毫无疑问，
从前向后遍历。
int rob(int* nums, int numsSize) { if(numsSize==1) return *nums; int dp[numsSize]; dp[0]=nums[0]; dp[1]=fmax(nums[0],nums[1]); for(int i=2;i<numsSize;i++) { dp[i]=fmax(dp[i-2]+nums[i],dp[i-1]); } return fmax(dp[numsSize-1],dp[numsSize-2]); }
Leetcode——740.删除并获得点数
给你一个整数数组 nums ，你可以对它进行一些操作。
每次操作中，选择任意一个 nums[i] ，删除它并获得 nums[i] 的点数。之后，你必须删除 所有 等于 nums[i] - 1 和 nums[i] + 1 的元素。
开始你拥有 0 个点数。返回你能通过这些操作获得的最大点数。
示例 1：
输入：nums = [3,4,2]
输出：6
解释：
删除 4 获得 4 个点数，因此 3 也被删除。
之后，删除 2 获得 2 个点数。总共获得 6 个点数。
示例 2：
输入：nums = [2,2,3,3,3,4]
输出：9
解释：
删除 3 获得 3 个点数，接着要删除两个 2 和 4 。
之后，再次删除 3 获得 3 个点数，再次删除 3 获得 3 个点数。
总共获得 9 个点数。
这一题可看作是打家劫舍的变种
可以定义一个数组用于记录数字的个数，然后按照数字排序的位序来进行打家劫舍问题解决。
int deleteAndEarn(int* nums, int numsSize) { int ma[10001]={0}; int dp[10001]={0}; for(int i=0;i<numsSize;i++) { ma[nums[i]]++; } dp[1]=ma[1]; for(int i=2;i<=10000;i++) { dp[i]=fmax(dp[i-1],dp[i-2]+ma[i]*i); } return dp[10000]; }
矩阵类型：
Leetcode——62.不同路径
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
问总共有多少条不同的路径？
示例 1：
输入：m = 3, n = 7
输出：28
示例 2：
输入：m = 3, n = 2
输出：3
解释：
从左上角开始，总共有 3 条路径可以到达右下角。
- 向右 -> 向下 -> 向下
- 向下 -> 向下 -> 向右
- 向下 -> 向右 -> 向下
示例 3：
输入：m = 7, n = 3
输出：28
示例 4：
输入：m = 3, n = 3
输出：6
我们将所有的 f(0,j) 以及 f(i,0) 都设置为边界条件，它们的值均为 1；
由于我们每一步只能从向下或者向右移动一步，因此要想走到 (i,j)，如果向下走一步，那么会从 (i−1,j) 走过来；如果向右走一步，那么会从 (i,j−1) 走过来；
动态规划转移方程：f(i, j) = f(i-1, j) + f(i, j-1)；
最终的答案即为 f(m-1,n-1).
复杂度分析
时间复杂度：O(mn)。
空间复杂度：O(mn)，即为存储所有状态需要的空间。注意到 f(i,j) 仅与第 i 行和第 i−1 行的状态有关，因此我们可以使用滚动数组代替代码中的二维数组，使空间复杂度降低为 O(n)；
此外，由于我们交换行列的值并不会对答案产生影响，因此我们总可以通过交换 m 和 n 使得 m≤n，这样空间复杂度降低至 O(min(m,n))。
int uniquePaths(int m, int n) { int l[m][n]; for(int i=0;i<m;++i) { l[i][0]=1; } for(int j=0;j<n;++j) { l[0][j]=1; } for(int i=1;i<m;++i) { for(int j=1;j<n;++j) { l[i][j]=l[i-1][j]+l[i][j-1]; } } return l[m-1][n-1]; }
Leetcode——64.最小路径和
给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
说明：每次只能向下或者向右移动一步。
示例 1：
输入：grid = [[1,3,1],[1,5,1],[4,2,1]]
输出：7
解释：因为路径 1→3→1→1→1 的总和最小。
示例 2：
输入：grid = [[1,2,3],[4,5,6]]
输出：12
于路径的方向只能是向下或向右，因此网格的第一行的每个元素只能从左上角元素开始向右移动到达，网格的第一列的每个元素只能从左上角元素开始向下移动到达，此时的路径是唯一的，因此每个元素对应的最小路径和即为对应的路径上的数字总和。
对于不在第一行和第一列的元素，可以从其上方相邻元素向下移动一步到达，或者从其左方相邻元素向右移动一步到达，元素对应的最小路径和等于其上方相邻元素与其左方相邻元素两者对应的最小路径和中的最小值加上当前元素的值。由于每个元素对应的最小路径和与其相邻元素对应的最小路径和有关，因此可以使用动态规划求解。
创建二维数组 dp，与原始网格的大小相同，dp[i][j] 表示从左上角出发到 (i,j) 位置的最小路径和。显然，dp[0][0]=grid[0][0]。对于 dp 中的其余元素，通过以下状态转移方程计算元素值。
当 i>0 且 j=0 时，dp[i][0]=dp[i−1][0]+grid[i][0]。
当 i=0 且 j>0 时，dp[0][j]=dp[0][j−1]+grid[0][j]。
当 i>0 且 j>0 时，dp[i][j]=min(dp[i−1][j],dp[i][j−1])+grid[i][j]。
最后得到 dp[m−1][n−1] 的值即为从网格左上角到网格右下角的最小路径和。
int minPathSum(int** grid, int gridSize, int* gridColSize) { int dp[gridSize][gridColSize[0]]; dp[0][0]=grid[0][0]; for(int i=1;i<gridSize;i++) { dp[i][0]=dp[i-1][0]+grid[i][0]; } for(int j=1;j<gridColSize[0];j++) { dp[0][j]=dp[0][j-1]+grid[0][j]; } for(int i=1;i<gridSize;i++) { for(int j=1;j<gridColSize[0];j++) { dp[i][j]=fmin(dp[i-1][j],dp[i][j-1])+grid[i][j]; } } return dp[gridSize-1][gridColSize[0]-1]; }