【每日刷题】Day122

【每日刷题】Day122

个人主页：开敲

所属专栏：每日刷题

文章目录

1. 376. 摆动序列 - 力扣（LeetCode）

2. 174. 地下城游戏 - 力扣（LeetCode）

1. 376. 摆动序列 - 力扣（LeetCode）

//思路：子序列动态规划问题。

//本题与 Day121 中 "环绕字符串中的唯一子字符串" 很相似，不过本题没有那么多的细节处理。

class Solution {

public:

    int wiggleMaxLength(vector<int>& nums)

    {

        int n = nums.size(),ans = 0;

        if(n==1) return 1;

        vector<int> dp(n,1);

        if(nums[1]-nums[0]) dp[1]++;

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

        {

            int max = 1;

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

            {

                if((nums[i]-nums[j])*(nums[j]-nums[j-1])<0)

                {

                    max = max>dp[j]?max:dp[j];

                    dp[i] = dp[i]>(max+1)?dp[i]:(max+1);

                }

                else if(nums[i]-nums[j]) dp[i] = dp[i]>2?dp[i]:2;

            }

        }

        for(int i = 0;i<n;i++) ans = ans>dp[i]?ans:dp[i];

        return ans;

    }

};

2. 174. 地下城游戏 - 力扣（LeetCode）

//思路：路径动态规划问题。

//本题不同于之前的路径问题，本题的思路为：以 某一位置 为起点时 到达终点。

class Solution {

public:

    const int INF = 0x3f3f3f3f;

    int calculateMinimumHP(vector<vector<int>>& dungeon)

    {

        int rows = dungeon.size(),cols = dungeon[0].size();

        vector<vector<int>> dp(rows+1,vector<int>(cols+1,INF));

        dp[rows][cols-1] = dp[rows-1][cols] = 1;

        for(int i = rows-1;i>=0;i--)

        {

            for(int j = cols-1;j>=0;j--)

            {

                dp[i][j] = min(dp[i][j+1],dp[i+1][j])-dungeon[i][j];

                dp[i][j] = max(1,dp[i][j]);//处理负血进入魔法球房间的情况

            }

        }

        return dp[0][0];

    }

};