leetcode专项 动态规划入门

刷一下leetcode的动态规划专项，本篇博客为入门专项 传送门

第一天

509. 斐波那契数

AC代码：

class Solution {
    
public:
    int fib(int n) {
    
        if(n < 2) return n;
        if(n == 2) return 1;
        int a = 1, b = 1;
        int c;
        for(int i = 2; i < n; i++) {
    
            c = a;
            a = b;
            b = c + a;
        }
        return b;
    }
};

1137. 第 N 个泰波那契数

AC代码：

class Solution {
    
public:
    int tribonacci(int n) {
    
        if(n < 2) return n;
        if(n == 2) return 1;
        int a = 0, b = 1, c = 1;
        int d;
        for(int i = 2; i < n; i++) {
    
            d = c;
            c = a + b + c;
            a = b;
            b = d;
        }
        return c;
    }
};

第二天

70. 爬楼梯

这个递推公式和斐波那契有点像。。。

AC代码：

class Solution {
    
public:
    int climbStairs(int n) {
    
        if(n <= 3) return n;
        int a = 2, b = 3;
        int c;
        for(int i = 4; i <= n; i++) {
    
            c = b;
            b = a + b;
            a = c;
        }
        return b;
    }
};

746. 使用最小花费爬楼梯

最小花费问题，写出状态转移方程即可

AC代码：

class Solution {
    
public:
    int minCostClimbingStairs(vector<int>& cost) {
    
        int h = cost.size();
        int w[1010];
        memset(w, 0, sizeof(w));
        for(int i = 2; i <= h; i++)
            w[i] = min(cost[i - 2] + w[i - 2], cost[i - 1] + w[i - 1]);
        return w[h];
    }
};

第三天

198. 打家劫舍

AC代码：

class Solution {
    
public:
    int rob(vector<int>& nums) {
    
        int m = nums.size();
        int f[110], g[110];
        memset(f, 0, sizeof(f));
        memset(g, 0, sizeof(g));
        f[0] = nums[0];
        for(int i = 1; i < m; i++) {
    
            f[i] = g[i - 1] + nums[i];
            g[i] = max(f[i - 1], g[i - 1]);
        }
        return max(f[m - 1], g[m - 1]);
    }
};

213. 打家劫舍 II