[数据结构与算法]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

和打家劫舍类似，多了个条件是：起点和终点不能同时选
枚举一下：1. 不选起点 2. 选起点 求公共最大值即可
AC代码：

const int N = 110;
int f[110], g[110];

class Solution {
public:
    int rob(vector<int>& nums) {
        if(nums.size() == 1) return nums[0];
        int m = nums.size();
        memset(f, 0, sizeof f);
        memset(g, 0, sizeof g);
        // 枚举一下起点
        int res = 0;
        // 第一种情况是 不选 起点
        for(int i = 1; i < m; i++) {
            f[i] = g[i - 1] + nums[i];
            g[i] = max(f[i - 1], g[i - 1]);
        }
        // 最终结果 选、不选终点 均可
        res = max(f[m - 1], g[m - 1]);
        // 第二种情况是 选 起点
        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]);
        }
        // 最终结果只能 不选终点，再与上一种情况的res取最大值即可
        res = max(res, g[m - 1]);
        return res;
    }
};

740. 删除并获得点数

打家劫舍的转化版，其实限制相同，要转化一下
可以将给的数组映射到1～10000的区间上（有限制的选择问题，此题也是不能选择相邻）
选1个 i 和 选2个 i 的影响是相同的，所以仅需考虑 i 选与不选即可

AC代码：

const int N = 10010;
int cnt[N], f[N][2];

class Solution {
public:
    int deleteAndEarn(vector<int>& nums) {
        memset(cnt, 0, sizeof cnt);
        memset(f, 0, sizeof f);
        for(auto x:nums)
            cnt[x]++;
        for(int i = 1; i < N; i++) {
            f[i][0] = max(f[i - 1][0], f[i - 1][1]);
            f[i][1] = f[i - 1][0] + cnt[i] * i;
        }
        // 也可以在循环中加一个res，每次都取max(f[i][0], f[i][1])，最后直接输出res
        return max(f[10009][1], f[10009][0]);
    }
};