完成日期：7月25日
总结：
- 动态规划5要素：状态定义，转移方程，初始状态，返回值，简化空间复杂度
- 想清楚dp[i]、dp是代表什么含义，然后想清楚状态转移方程
- 题目出现“最”字，可以联想是不是DP
- *min_element(res[m-1].begin(), res[m-1].end())
70. 爬楼梯
超简单的动态规划: f(x)=f(x−1)+f(x−2)
还有一种数学方法：矩阵快速幂，时间复杂度可以O(log n)
class Solution {
public:
int climbStairs(int n) {
if(n==1) return 1;
if(n==2) return 2;
int a = 1, b=2, res;
for(int i=2; i<n; ++i){
res = a+b;
a = b;
b = res;
}
return res;
}
};
198. 打家劫舍
动态规划：dp[i]=max(dp[i−2]+nums[i],dp[i−1])
class Solution {
public:
int rob(vector<int>& nums) {
int len = nums.size();
if(len == 1) return nums[0];
if(len == 2) return max(nums[0], nums[1]);
int res = 0;
int a = nums[0], b = max(nums[0], nums[1]);
for(int i = 2; i<len; ++i){
res = max(b, a + nums[i]);
a = b;
b = res;
}
return res;
}
};
120. 三角形最小路径和
// 使用二维数组占内存超大
class Solution {
public:
int minimumTotal(vector<vector<int>>& triangle) {
int m = triangle.size();
vector<vector<int>> res(m, vector<int>(m));
res[0][0] = triangle[0][0];
for (int i=1; i<m; ++i){
int n = triangle[i].size();
for(int j =0; j<n; j++){
if(j==0){
res[i][j] = triangle[i][j]+res[i-1][j];
}else if(j==n-1){
res[i][j] = triangle[i][j]+res[i-1][j-1];
}else{
res[i][j] = triangle[i][j]+min(res[i-1][j], res[i-1][j-1]);
}
}
}
return *min_element(res[m-1].begin(), res[m-1].end());
}
};
// 上面的二维数组空间复杂度O(n^2)
// 其实结果只与上一层相关，所以只需要记录2个一维数组，更简洁的，只需要1个一维数组（注意！要倒序遍历才行）
class Solution {
public:
int minimumTotal(vector<vector<int>>& triangle) {
int n = triangle.size();
vector<int> f(n);
f[0] = triangle[0][0];
for (int i =1; i<n; ++i){
f[i] = f[i-1] + triangle[i][i];
for(int j =i-1; j>0; --j){
f[j] = min(f[j], f[j-1]) + triangle[i][j];
}
f[0] = f[0] + triangle[i][0];
}
return *min_element(f.begin(), f.end());
}
};
还可以简化：从底向上计算，可以不需最后去算最小值
