完成日期：7月25日
总结：

1. 动态规划5要素：状态定义，转移方程，初始状态，返回值，简化空间复杂度
2. 想清楚dp[i]、dp是代表什么含义，然后想清楚状态转移方程
3. 题目出现“最”字，可以联想是不是DP
4. *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());
    }
};

还可以简化：从底向上计算，可以不需最后去算最小值