动态规划做题笔记_待整理
不同的路径
一个非常简单的DP题。分析三要素，写出状态转移方程如下：
f[i][j] = f[i - 1][j] + f[i][j - 1]
根据动态方程，可以知道当前状态由 i-1 行的第j列，与当前行第 i 行的前一列 j-1 决定。
因此，对于f[i - 1][j]，需要保存一个一维数组，用来记录前一行每列的最优值。
对于f[i][j - 1]只需要用前一个替换就行。（即上一个循环中的f[i][j]）
三角形问题
[LeetCode] Triangle 三角形
DP解决，假设第i，j的最优值为f[i][j]，从上往下，第二行开始，状态转移方程为
f[i][j] = min(f[i - 1][j - 1], f[i - 1][j]) + （i，j）
但是因为三角形，每一行数组长度不一样，又要求空间复杂度是O(n)，所以按照上一题的解法，是不可行的（因为上一题是维护一个相同shape的数组）。所以第一种方法，就是直接改动三角形数组的值。
但是这种方法，会改动原数据，不完美。于是有第二种方法，复制最后一行数组，在复制的一维数组中，从下往上的运行DP。。具体方法见参考。
最大子数组的和
[LeetCode] Maximum Subarray 最大子数组
举例[-2,1,-3,4,-1,2,1,-5,4]
如果用动态规划做，是比较简单的一道题。
参考soulmachine的LeetCode题解，讲的比较清楚了。
需要比较深刻的理解并总结规律。（这道题只让输出最大和，并没有让同时输出子数列）
对于数组里的一个整数，它只有两种选择 ：1、加入之前的SubArray；2、自己另起一个SubArray，作为SubArray的开头。那么什么时候会出现这两种情况呢？
这时候不是说，要判断子数列是否是最大值时再相加。（若是有最大值，在出现的时候，就已经被res保存了，这里只单纯的讨论，这个数要不要加到SubArray中去）
- 如果SubArray总体和大于0，那么这个子数列对于后续结果是有贡献的。
- 如果SubArray总体和小于0，那么这个子数列对于后续结果没有贡献甚至有害，此时，我们选择以这个数字作为开始重新另起一个SubArray。
比如，前面数组中，-2小于0，那么这个SubArray加上后面的，也是会损害总体和的。所以应该舍弃，从1开始另起一个SubArray。
1大于0，那么只要是加上后面的说，就一定会使SubArray往好的方向发展。
[1,-3]小于0，所以应该再从4开始。
假设 f[j] 代表当前以第 j 个元素为结尾的SubArray的和，S[j] 代表数组的第j个元素。
那么怎么将上述的解释，转化成状态转移方程呢。
-
转换一下思路，上面就是对于f[j]来说，就两种可能，一是取f[j-1] + S[j]，二是取S[j]。所以直接就是，取其中最大值即可。
-
最大值，就是在j从0到最后期间，出现的最大值。
于是可以得到状态转移方程：
res为最终结果，cur为当前值
先用sys.maxsize，获得最小整数，对res进行赋值。cur赋初值为0.
Python获取最大最小整数值参考Python 小技巧：Python3 表示最大整数值和浮点数值
于是可以有(C++代码）
int res = INT_MIN, curSum = 0;
for (int num : nums) {
curSum = max(curSum + num, num);
res = max(res, curSum);
拆分回文串2
[LeetCode] Palindrome Partitioning II 拆分回文串之二
暂时没看懂。。。
最大矩形问题、、、
都是hard题，劝退，劝退。
