C++算法第十六天

本篇文章我们继续学习动态规划

第一题

题目链接

978. 最长湍流子数组 - 力扣（LeetCode）

题目解析

从上图可见其实有三个状态

代码原理

注意：我们在分析题目的时候分析出来的是三个状态，分别是上升、下降、平坦，但是不一定要定义三个状态表示，一个不够加一个，直到可以解决这道题为止

代码编写

class Solution {

public:

    int maxTurbulenceSize(vector<int>& arr) {

        int n = arr.size();

        vector<int> f(n, 1);

        auto g = f;

        int ret = 1;

        for(int i = 1; i < n; i++)

        {

            if(arr[i] > arr[i - 1])f[i] = g[i - 1] + 1;

            else if(arr[i] < arr[i - 1])g[i] = f[i - 1] + 1;

            ret = max(ret, max(f[i], g[i]));

        }

        return ret;

    }

};

第二题

题目链接

413. 等差数列划分 - 力扣（LeetCode）

题目解析

代码原理

代码编写

class Solution {

public:

    int numberOfArithmeticSlices(vector<int>& nums) {

        int n = nums.size();

        vector<int> dp(n);

        int count = 0;

        for(int i = 2; i < n; i++)

        {

            dp[i] = nums[i] - nums[i - 1] == nums[i - 1] - nums[i - 2]? dp[i - 1] + 1:0;

            count += dp[i];

        }

        return count;

    }

};

第三题

题目链接

139. 单词拆分 - 力扣（LeetCode）

题目解析

代码原理

代码编写

class Solution {

public:

    bool wordBreak(string s, vector<string>& wordDict) {

        unordered_set<string> hash;

        for(auto cur: wordDict) hash.insert(cur);

        int n = s.size();

        vector<bool>dp(n + 1);

        dp[0] = true;

        s = ' ' + s;//保证字符串的长度与dp表的长度一致

        for(int i = 1; i <= n; i++)

        {

            for(int j = i; j >= 1; j--)

            {

                if(dp[j - 1] && hash.count(s.substr(j, i - j + 1)))

                {

                    dp[i] = true;

                    break;

                }

            }

        }

        return dp[n];

    }

};

本篇文章的内容就先到这里，我们下期文章再见！！！

记得一键三联哦！！！