当前位置：网站首页>Introduction to leetcode special dynamic planning

Introduction to leetcode special dynamic planning

2022-07-18 17:10:00 【Well, let me see】

Brush it. leetcode Dynamic planning project of , This blog is an introductory project Portal

leetcode special Introduction to dynamic planning

The first day

509. Fibonacci number

AC Code ：

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. The first N One tibonacci number

AC Code ：

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;
    }
};

the second day

70. climb stairs

This recursive formula is a bit like Fibonacci ...

AC Code ：

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. Use the minimum cost to climb the stairs

Minimum cost problem , Write the state transition equation

AC Code ：

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];
    }
};

On the third day

198. raid homes and plunder houses

Insert picture description here
AC Code ：

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]);
    }
};