每周算法:斐波那契数列模型+路径问题+简单多状态dp+子数组系列

啊QQQQQ

发布于 2024-11-19 19:20:54

1860

文章被收录于专栏：C++C++

一.斐波那契数列模型

1.1第N个斐波那契数

题目地址:. - 力扣（LeetCode）

泰波那契序列 Tn 定义如下：

T0 = 0, T1 = 1, T2 = 1, 且在 n >= 0 的条件下 Tn+3 = Tn + Tn+1 + Tn+2

给你整数 n，请返回第 n 个泰波那契数 Tn 的值。

示例 1：

输入：n = 4
输出：4
解释：
T_3 = 0 + 1 + 1 = 2
T_4 = 1 + 1 + 2 = 4

示例 2：

输入：n = 25
输出：1389537f

分析

这道题不同于斐波那契数列的是递推公式变成了前三个数相加;题目的思路都已经给出了,所以我们只需要处理好边界就可以了;

再来复习下动态规划的模版: 1.创建dp表;---这道题就是Tn下标是0~n所以要开n+1个空间; 2.初始化,---题目已经给出; 3.写出状态转移方程---dp[i]=dp[i-1]+dp[i-2]+dp[i-3]; 4.填表--可能会同时填多个dp表; 4.返回值---这道题就是直接返回dp[n];

题解

class Solution {
public:
    int tribonacci(int n) {
        //1.创建dp表
        //2初始化
        //3.状态转移方程
        //4.返回值

        //如果前三个默认值就直接返回即可
        if(n==0)return 0;
        if(n==1||n==2)return 1;
         //创建dp表
         vector<int>dp(n+1);
        //初始化
         dp[0]=0;dp[1]=dp[2]=1;
        //填表
        for(int i=3;i<=n;i++)
        dp[i]=dp[i-1]+dp[i-2]+dp[i-3];
        //返回值
        return dp[n];
    }
};

1.2三步问题

题目地址:. - 力扣（LeetCode）

三步问题。有个小孩正在上楼梯，楼梯有n阶台阶，小孩一次可以上1阶、2阶或3阶。实现一种方法，计算小孩有多少种上楼梯的方式。结果可能很大，你需要对结果模1000000007。

示例1:

 输入：n = 3 
 输出：4
 说明: 有四种走法

示例2:

 输入：n = 5
 输出：13

提示:

n范围在[1, 1000000]之间

分析

要上到第n阶台阶,只能从第n-1,n-2,n-3级台阶上跳上去;以dp[i]表示套上第i级台阶的跳法,那么状态转移方程就是dp[i]=dp[i-1]+dp[i-2]+dp[i-3];

我们一般创建dp表时,按照经验都是需要在表的最前面开一个虚拟节点的;填完表直接返回即可;

这道题的结果取的是后mod位,mod=1e9+7;我们在填表的过程可能会因为数据大超过mod,所以每次+后都要记得%mod;

我在写时候出现了些小问题:没有首先判断默认值!

为什么会这样呢?

如果n==1时,我下面开的dp数组是dp(2);但是我初始化数组时,dp[2] 此时是越界的;代码就会崩掉; 建议:为了防止上述情况出现,我们注意默认值记得先判断一下哦;

题解

class Solution {
public:
const int mod=1e9+7;
    int waysToStep(int n) {
        if(n==1||n==2)return n;//返回默认值
        vector<int>dp(n+1);
        dp[0]=dp[1]=1;dp[2]=2;
        for(int i=3;i<=n;i++)
        dp[i]=((dp[i-1]+dp[i-2])%mod+dp[i-3])%mod;
        return dp[n];
    }
};

二.路径问题(矩阵dp)

2.1不同路径

题目地址:. - 力扣（LeetCode）

一个机器人位于一个 m x n 网格的左上角（起始点在下图中标记为 “Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。

问总共有多少条不同的路径？

示例 1：

输入：m = 3, n = 7
输出：28

示例 2：

输入：m = 3, n = 2
输出：3
解释：
从左上角开始，总共有 3 条路径可以到达右下角。
1. 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右
3. 向下 -> 向右 -> 向下

示例 3：

输入：m = 7, n = 3
输出：28

示例 4：

输入：m = 3, n = 3
输出：6

提示：

1 <= m, n <= 100
题目数据保证答案小于等于 2 * 109

分析

这道题与爬楼梯类似,要到达(i,j)格子就只能是从(i-1,j)和(i,j-1)格子跳过来;那么状态转移方程也就是跳到(i,j)格子的总跳法就是:dp[i][j]=dp[i-1][j]+dp[i][j-1]了;

填表:观察我们的状态转移方程,如果我们dp[0][0],那是会越界的,所以我们通常会在行和列加上一层的虚拟节点;将虚拟节点全部初始化为0,注意这里dp[1][1]初始化为1;

题解

class Solution {
public:
    int uniquePaths(int m, int n) {
        vector<vector<int>>dp(m+1,vector<int>(n+1,0));
        for(int i=1;i<=m;i++)
        {
            for(int j=1;j<=n;j++)
            {
                if(i==j&&i==1)dp[i][j]=1;
                else
                dp[i][j]=dp[i-1][j]+dp[i][j-1];
            }
        }
        return dp[m][n];
    }
};

2.2珠宝的最大价值

题目地址:. - 力扣（LeetCode）

现有一个记作二维矩阵 frame 的珠宝架，其中 frame[i][j] 为该位置珠宝的价值。拿取珠宝的规则为：

只能从架子的左上角开始拿珠宝
每次可以移动到右侧或下侧的相邻位置
到达珠宝架子的右下角时，停止拿取

注意：珠宝的价值都是大于 0 的。除非这个架子上没有任何珠宝，比如 frame = [[0]]。

示例 1:

输入: frame = [[1,3,1],[1,5,1],[4,2,1]]
输出:12
解释: 路径 1→3→5→2→1 可以拿到最高价值的珠宝

提示：

0 < frame.length <= 200
0 < frame[0].length <= 200

分析

到(i,j)格子所获得的最大珠宝价值,就是从左边和上边挑一个大的,然后加上自己格子的珠宝价值;

状态转移方程:dp[i][j]=max(dp[i-1][j],dp[i][j-1])+f[i-1][j-1];这里注意了,我们自己格子的珠宝价值对应原数组的位置是[i-1,j-1];

题解

class Solution {
public:
    int jewelleryValue(vector<vector<int>>& f) {
        int m=f.size();int n=f[0].size();
        vector<vector<int>>dp(m+1,vector<int>(n+1,0));//将虚拟节点全部初始化为0
        for(int i=1;i<=m;i++)
        {
            for(int j=1;j<=n;j++)
            {
                dp[i][j]=max(dp[i-1][j],dp[i][j-1])+f[i-1][j-1];
            }
        }
        return dp[m][n];
    }
};

三.简单多状态dp

3.1打家劫舍

题目地址:. - 力扣（LeetCode）

一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响小偷偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组 nums ，请计算 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

示例 1：

输入：nums = [1,2,3,1]
输出：4
解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
     偷窃到的最高金额 = 1 + 3 = 4 。

示例 2：

输入：nums = [2,7,9,3,1]
输出：12
解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
     偷窃到的最高金额 = 2 + 9 + 1 = 12 。

分析

还是常用的思想,dp[i]代表以i位置结尾的最大金额数,在i这个位置有偷和不偷两种状态,我们的目的就是找出与前一个问题的联系;

这道题不同的是,他有两个dp表,对于这种状态我们有两种方式处理;

1.给数组多加一列用来标记状态;就是我下面使用的方法;

2.创建f,g表(一维数组),f[i]是i位置偷时获得的最大金额;g[i]是i位置不偷时,获得的最大金额,那么i位置获得的最大金额就是二者取大的max(f[i],g[i])啦;

题解

class Solution {
public:
    int rob(vector<int>& nums) {
        int n=nums.size();
        vector<vector<int>>dp(n+1,vector<int>(2));
        for(int i=1;i<=n;i++)
        {
            //如果不偷,那现金数取决于前面的
            dp[i][0]=max(dp[i-1][0],dp[i-1][1]);
            //如果偷的话
            dp[i][1]=dp[i-1][0]+nums[i-1];
        }
        return max(dp[n][0],dp[n][1]);
    }
};

3.2粉刷房子

题目地址:. - 力扣（LeetCode）

假如有一排房子，共 n 个，每个房子可以被粉刷成红色、蓝色或者绿色这三种颜色中的一种，你需要粉刷所有的房子并且使其相邻的两个房子颜色不能相同。

当然，因为市场上不同颜色油漆的价格不同，所以房子粉刷成不同颜色的花费成本也是不同的。每个房子粉刷成不同颜色的花费是以一个 n x 3 的正整数矩阵 costs 来表示的。

例如，costs[0][0] 表示第 0 号房子粉刷成红色的成本花费；costs[1][2] 表示第 1 号房子粉刷成绿色的花费，以此类推。

请计算出粉刷完所有房子最少的花费成本。

示例 1：

输入: costs = [[17,2,17],[16,16,5],[14,3,19]]
输出: 10
解释: 将 0 号房子粉刷成蓝色，1 号房子粉刷成绿色，2 号房子粉刷成蓝色。
     最少花费: 2 + 5 + 3 = 10。

分析

题解

class Solution {
public:
    int minCost(vector<vector<int>>& costs) {
        int n=costs.size();
        vector<vector<int>>dp(n+1,vector<int>(3));
        for(int i=1;i<=n;i++)
        {
            dp[i][0]=min(dp[i-1][1],dp[i-1][2])+costs[i-1][0];
            dp[i][1]=min(dp[i-1][0],dp[i-1][2])+costs[i-1][1];
            dp[i][2]=min(dp[i-1][1],dp[i-1][0])+costs[i-1][2];
        }
        return min(dp[n][0],min(dp[n][1],dp[n][2]));
    }
};

四.子数组系列

4.1最大子数组和

题目地址:. - 力扣（LeetCode）

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

子数组

是数组中的一个连续部分。

示例 1：

输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。

示例 2：

输入：nums = [1]
输出：1

子数组概念

什么是子数组,子数组就是数组中连续位置的几个数;比如[2,5,4,6],那么子数组就是[2],[5],[4],[6],[2,5],[2,5,4],[5,4,6]等等,位置必须是挨着的,一个数也是子数组;

分析

我们要找最大的子数组的和,对于以i位置结尾的数,有两个选择 1.选择跟前面的数拼接 2.自己作为子数组的第一个元素; 那我们就取较大的情况就是最大的子数组的和了;

题解

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
     int n=nums.size();
     vector<int>dp(n+1);
     int ret=INT_MIN;
     for(int i=1;i<=n;i++)
     {
        if(dp[i-1]>=0)
        dp[i]=dp[i-1]+nums[i-1];
        else
        dp[i]=nums[i-1];//要么连上前面的要么自己重新开一个序列
        ret=max(ret,dp[i]);
     }   
     return ret;
    }
};

4.2环形最大子数组和

题目地址:. - 力扣（LeetCode）

给定一个长度为 n 的环形整数数组 nums ，返回 nums 的非空 子数组 的最大可能和 。

环形数组 意味着数组的末端将会与开头相连呈环状。形式上， nums[i] 的下一个元素是 nums[(i + 1) % n] ， nums[i] 的前一个元素是 nums[(i - 1 + n) % n] 。

子数组 最多只能包含固定缓冲区 nums 中的每个元素一次。形式上，对于子数组 nums[i], nums[i + 1], ..., nums[j] ，不存在 i <= k1, k2 <= j 其中 k1 % n == k2 % n 。

示例 1：

输入：nums = [1,-2,3,-2]
输出：3
解释：从子数组 [3] 得到最大和 3

示例 2：

输入：nums = [5,-3,5]
输出：10
解释：从子数组 [5,5] 得到最大和 5 + 5 = 10

分析

这道题是上一道题的升级版;基本思路差不多;

最后返回值有两种情况

1.返回max(最大子数组和,sum-最小子数组和); 2.如果sum==最小子数组和,那就直接返回_max;

为什么会sum==最小子数组和?

如果数组全是负数,那么正确结果应该是数组中最大的那一个数,也就是最大子数组和;但是这个时候sum-最小子数组和=0;显然这道题结果不是0;当sum==最小子数组和时,就不符合题意了,所以要特殊判断一下;

题解

class Solution {
public:
    int maxSubarraySumCircular(vector<int>& nums) {
        int n=nums.size();int sum=0;
        //分别数组的最大子数组和和最小子数组和
        int _max=INT_MIN;int _min=INT_MAX;
        for(auto &x:nums)sum+=x;
        vector<int>dp1(n+1);
        auto dp2=dp1;
        for(int i=1;i<=n;i++)
        {
            dp1[i]=max(dp1[i-1]+nums[i-1],nums[i-1]);
            _max=max(_max,dp1[i]);
            dp2[i]=min(dp2[i-1]+nums[i-1],nums[i-1]);
            _min=min(_min,dp2[i]);
        }
        if(_min==sum)return _max;
        return max(_max,sum-_min);
    }
};

后续每周我可能还会尽力更新多种类型的动态规划例题,慢慢进步!

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2024-11-19，如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

登录后参与评论

0 条评论

热度