LeetCode.70.198.120(动态规划)

终于有点明白了为什么动规叫做用空间换时间

70.爬楼梯

原来写过，又写了一遍，发现果然忘了==

#include <vector>
using namespace std;
class Solution {
  public:
    int climbStairs(int n) {
        int times = 1, temp1 = 0, temp2 = 0;
        for (int i = 0; i < n; i++) {
            temp2 = times;
            times += temp1;
            temp1 = temp2;
        }
        return times;
    }
    // 45/45 cases passed (0 ms)
    // Your runtime beats 100 % of cpp submissions
    // Your memory usage beats 71.84 % of cpp submissions (5.8 MB)
    /**
     * 就跟斐波那契数列差不多，
     * n=1 踏上1阶直接结束
     * n=2 1+1 2 times=2
     * n=3 1+1+1 1+2 2+1 times=3 可以看做n=2+1
     * 恰好这里第n个台阶的times=n-1个台阶的times + 第n-2个台阶的times，成斐波那契数列
     */
    /*int times = 0;
    void fun(int n) {
        if (n == 0) {
            times += 1;
            return;
        }
        if (n < 0) {
            return;
        }
        fun(n - 1);
        fun(n - 2);
    }*/
    /*int climbStairs(int n) {
        fun(n);
        int c = times;
        times = 0;
        return c;
        //直接超时，算是能算的出来，计算的速度我肉眼都能识别了。。。
        if (n <= 2) {
            return n;
        }
        return climbStairs(n - 1) + climbStairs(n - 2);
        //也是自己想的，和上面半斤八两
        //以下是官方solution
        //动态规划：
        int p = 0, q = 0, r = 1;
        for (int i = 0; i < n; i++) {
            p = q;
            q = r;
            r = p + q;
        }
        return r;
    }*/
};

198.打家劫舍

class Solution {
  public:
    int rob(vector<int> &nums) {
        vector<int> r(max((int)nums.size(), 2), 0);
        r[0] = nums[0];
        r[1] = max(nums[0], nums.size() >= 2 ? nums[1] : 0);
        int Max = r[1];
        for (int i = 2; i < nums.size(); i++) {
            int q = 0;
            for (int j = 0; j < i - 1; j++) {
                q = max(q, nums[i] + r[j]);
            }
            r[i] = q;
            Max = max(Max, q);
        }
        return Max;
        // 68/68 cases passed (0 ms)
        // Your runtime beats 100 % of cpp submissions
        // Your memory usage beats 62.18 % of cpp submissions (7.5 MB)
    }
};

120.三角形最小路径和

class Solution {
  public:
    int minimumTotal(vector<vector<int>> &triangle) {
        for (int i = triangle.size() - 2; i >= 0; i--) {
            for (int j = 0; j < triangle[i].size(); j++) {
                int temp = 0;
                triangle[i][j] += min(triangle[i + 1][j], triangle[i + 1][j + 1]);
            }
        }
        return triangle[0][0];
        // 44/44 cases passed (4 ms)
        // Your runtime beats 93.52 % of cpp submissions
        // Your memory usage beats 76.28 % of cpp submissions (8.4 MB)
    }
};