建设部网站证书查询,设计师接私单做网站,做网站资料准备,宁波网站建设哪里有斐波那契数列模型以及多状态 动态规划简述斐波那契数列模型1.第 N 个泰波那契数#xff08;简单#xff09;2.三步问题#xff08;简单#xff09;3.使⽤最⼩花费爬楼梯#xff08;简单#xff09;4.解码方法#xff08;中等#xff09; 简单多状态1.打家劫舍#xff… 斐波那契数列模型以及多状态 动态规划简述斐波那契数列模型1.第 N 个泰波那契数简单2.三步问题简单3.使⽤最⼩花费爬楼梯简单4.解码方法中等 简单多状态1.打家劫舍中等2.打家劫舍II中等3.粉刷房子中等4.删除并获得点数中等5.买卖股票的最佳时期含⼿续费中等6.买卖股票的最佳时机含冷冻期中等7.买卖股票的最佳时机III困难8.买卖股票的最佳时机IV困难 动态规划简述 动态规划(Dynamic programming简称 DP)是一种解决多阶段决策问题的算法思想。它将问题分解为多个阶段并通过保存中间结果来避免重复计算从而提高效率。 动态规划的解题步骤一般分为以下几步
思考状态表示创建dp表(重点)分析出状态转移方程(重点)初始化确定填表顺序确定返回值 斐波那契数列模型
1.第 N 个泰波那契数简单
链接第 N 个泰波那契数
题目描述 做题步骤
状态表示 面对动态规划问题我们一般有两种状态表示 以某一个位置为起点……以某一个位置为终点…… 我们一般优先考虑第1种表示但如果第1种无法解决就考虑第2种。 状态转移方程 这个题目直接告诉了我们状态转移方程dp[i] dp[i - 1] dp[i - 2] dp[i - 3] 初始化 泰波那契数的第0、1、2个是特殊的不满足状态转移方程因此我们需要初始化这三个位置为0、1、1 填表顺序 保证填当前状态时所需状态已经计算过填表顺序很明显是从左往右 返回值 根据状态表示假设要求的是第n个返回的应该是dp[n]
代码实现
class Solution {
public:int tribonacci(int n) {//对于第0、1、2单独处理if(n 0) return 0;if(n 1 || n 2)return 1;//dp[i]第i个泰波那契数vectorint dp(n 1);dp[0] 0; dp[1] 1; dp[2] 1; for(int i 3; i n 1; i){dp[i] dp[i-1] dp[i-2] dp[i-3];}return dp[n];//空间复杂度O(N)//时间复杂度O(N)}
};//不知道大家有没有发现向后填表的过程其实只需要前置的3个状态
//其余的状态都是多余的我们可以用有限的变量来保存这些状态这样就实现了空间优化
//这种优化方式被称为“滚动数组”
//经过优化原O(N)-O(1) O(N^2)-O(N)
//但这并不是动态规划讲解的要点所以我只会把两种优化情况的代码给出// class Solution {
// public:
// int tribonacci(int n)
// {
// if(n 0)
// return 0;
// if(n 1 || n 2)
// return 1;// int t1 0;
// int t2 1;
// int t3 1;
// int ret 0;// for(int i 3; i n 1; i)
// {
// ret t1 t2 t3;
// t1 t2;
// t2 t3;
// t3 ret;
// }
// return ret;
// }
// };2.三步问题简单
链接三步问题 题目描述 做题步骤 状态表示 状态转移方程 到达i阶可以转换成先到达i - 3、i - 2、i - 1阶三者相加得到结果所以状态转移方程为dp[i] dp[i - 1] dp[i - 2] dp[i - 3]。 初始化 为了保证填表不越界我们把到达1、2、3阶的方法初始化。 填表顺序 保证填当前状态时所需状态已经计算过填表顺序从左往右。 返回值 根据状态表示假设要求的是n阶返回的应该是dp[n]
代码实现
class Solution {
public:int waysToStep(int n) {//1、2、3阶特殊处理if(n 1) return 1;if(n 2) return 2;if(n 3) return 4;//dp[i]表示到达i阶的方法数vectorint dp(n1); //多开一个空间可以让下标和层数对应dp[1] 1; dp[2] 2; dp[3] 4;const int mod 1e9 7; //有可能超出需要取模for(int i 4; i n 1; i){dp[i] ((dp[i-1] dp[i-2]) % mod dp[i-3]) % mod;}return dp[n];//时间复杂度O(N)//空间复杂度O(N)}
};3.使⽤最⼩花费爬楼梯简单
链接使⽤最⼩花费爬楼梯 题目描述 做题步骤 状态表示 这个题目的思路和第2题很相似要到达终点n阶我们可以从n - 1阶走一步、n - 2阶走两步到终点从中选择费用最低的一方(从当前阶离开需要支付离开费用)至于到达n - 1、n - 2阶的最低费用我们可以以n - 1、n - 2层为终点进行分析依此类推。到达终点的过程需要到达每一层的最低费用我们可以用一个dp表存储dp[i]表示到达下标i台阶所需要的最低费用。 状态转移方程 到达i阶的最低花费可以转换为min(到达i - 1阶的最低花费 走出这一阶的花费 到达i - 2阶的最低花费 走出这一阶的花费)所以状态转移方程为dp[i] min(dp[i - 1] cost[i - 1], dp[i - 2] cost[i - 2])。 初始化 由转移方程可知更新某个状态需要前置的两个状态为了确保填表时不越界单独处理走到0、1阶的最低花费。 填表顺序 保证填当前状态时所需状态已经计算过填表顺序从左往右。 返回值 根据状态表示假设数组有n个元素(终点是n阶)返回的应该是dp[n]
代码实现
class Solution {
public:int minCostClimbingStairs(vectorint cost) { //dp[i] 表示到这一层的最小花费int n cost.size();vectorint dp(n 1);//一开始就可以在0或1阶花费为0vector默认给0不用处理for(int i 2; i n 1; i){dp[i] min(dp[i-1] cost[i-1], dp[i-2] cost[i-2]);}return dp[n];//空间复杂度O(N)//时间复杂度O(N)}
};// //第二种写法反着来以某个位置为起点……
// class Solution {
// public:
// int minCostClimbingStairs(vectorint cost)
// {
// //dp[i]这一层为起点到终点的最低花费
// int n cost.size();
// vectorint dp(n 1);
// dp[n] 0;
// dp[n - 1] cost[n - 1];
// for(int i n - 2; i 0; i--)
// {
// dp[i] min(dp[i 1] cost[i], dp[i 2] cost[i]);
// }// return min(dp[0], dp[1]);
// }
// };4.解码方法中等
链接解码方法 题目描述 做题步骤 状态表示 状态表示 除去第一位每个位置都有单独解码和联合解码两种方式n位置的状态转移方程为dp[n] dp[n - 1]单独解码成功 dp[n - 2]联合解码成功 初始化 依据状态转移方程某位置状态需要前置的两个状态为了避免越界我们需要单独处理第1、2个位置但观察上面的分析过程可以发现第2个位置和其它位置一样也有两种解码可能我们可以在dp表前面多加个虚拟节点并初始为1这样就只需要处理第1个位置了。看图看图 填表顺序 保证填当前状态时所需状态已经计算过填表顺序从左往右。 返回值 依据状态定义假设序列长度为n返回的应该是以n位置为结尾的解码可能数即dp[n]。
代码实现
class Solution {
public:int numDecodings(string s) {int n s.size();//dp[i]表示以i位置为结尾的解码可能数vectorint dp(n 1);//第一个位置就为0最终结果已经是0if(s[0] 0)return 0;//初始化虚拟节点和第1个位置dp[1] dp[0] 1;for(int i 2; i n 1; i){//单独解码if(s[i - 1] ! 0) dp[i] dp[i-1];//联合解码联合解码小于10说明存在前导0无法联合解码int com (s[i - 2] - 0) * 10 (s[i - 1] - 0);if(com 10 com 26) dp[i] dp[i-2];//都失败的情况是00最终结果已经是0这里可不加//两个连续的0后面全都是0if(dp[i] 0)return 0; }return dp[n];}
};简单多状态
1.打家劫舍中等
链接打家劫舍 题目描述 做题步骤
状态表示 依据前面的做题经验我们可以把状态表示为以i位置为结尾的最大偷窃金额但每个位置有偷和不偷两种选择所以可以把状态再进行细化状态f表示以i位置为结尾并偷窃本位置的最大金额状态g表示以i位置为结尾但不偷窃本位置的最大金额。 状态转移方程 由前面的分析可知要偷i位置(f)需要i - 1位置不偷(g)的最大金额不偷i位置就选择i - 1位置偷和不偷两种选择中大的一方所以状态转移方程为(1) f[i] g[i - 1] nums[ i ] (本位置可偷金额)(2) g[i] max(g[i - 1], f[i - 1]) 初始化 由状态转移方程可知当今状态需要前一个状态为保证填表时不越界单独处理第一个位置f[0] nums[0]g[0] 0。 填表顺序 保证填当前状态时所需状态已经计算过填表顺序从左往右。 返回值 把自己代入成小偷相邻位置不能同时偷的情况下是需要进行选择的但偷的过程中不知道后面房子的价值只能走一步看一步保证每一步都是最好的偷到最后一定是最优结果。假设数组有n个元素返回值为max(f[n - 1], g[n - 1])。
代码实现
class Solution {
public:int rob(vectorint nums) {int n nums.size();vectorint f(n); //f[i]表示到底这个位置并偷窃的最大金额auto g f; //g[i]表示到达这个位置不偷窃的最大金额f[0] nums[0]; //初始化f[0],g[0]默认0不用处理for(int i 1; i n; i){f[i] g[i - 1] nums[i];g[i] max(g[i - 1], f[i - 1]);}return max(f[n - 1], g[n - 1]);//空间复杂度O(N)//时间复杂度O(N)}
};2.打家劫舍II中等
链接打家劫舍II 题目描述 做题步骤 状态表示 这个题和前一个题唯一的不同只有首尾成环这一个点我们延用上个题目的状态表示状态f表示以i位置为结尾并偷窃本位置的最大金额状态g表示以i位置为结尾但不偷窃本位置的最大金额。 处理成环问题最直接的思路就是拆解。 状态转移方程 和上一道题目一致状态转移方程为(1) f[i] g[i - 1] nums[ i ] (本位置可偷金额)(2) g[i] max(g[i - 1], f[i - 1]) 初始化 和上一道题目一致。 填表顺序 从左往右。 返回值 _rob函数表示指定区间的打家劫舍返回值为 max(nums[0] _rob(nums, 2, n - 2), _rob(nums, 1, n - 1))。
代码实现
class Solution {
public:int _rob(vectorint nums, int left,int right) {//区间不存在返回0if(left right)return 0;int n nums.size();vectorint f(n); //到这个屋子偷的最大金额auto g f; //到这个屋子不偷的最大金额f[left] nums[left];for(int i left 1; i right; i){f[i] g[i - 1] nums[i];g[i] max(f[i - 1],g[i - 1]);}return max(f[right],g[right]);}int rob(vectorint nums) {int n nums.size();return max(nums[0] _rob(nums, 2, n - 2), _rob(nums, 1, n - 1));}
};3.粉刷房子中等
链接粉刷房子 题目描述 做题步骤 状态表示 依据经验和题目要求我们可以把状态定义为把第i号房子粉刷成j颜色的最小花费。 状态转移方程 状态转移方程为(0是红色、1是蓝色、2是绿色) (1)dp[i][0] min(dp[i - 1][1], dp[i - 1][2]) cost[i][0]花费 (2)dp[i][1] min(dp[i - 1][0], dp[i - 1][2]) cost[i][1] (3)dp[i][2] min(dp[i - 1][0], dp[i - 1][1]) cost[i][2] 初始化 为了保证填表不越界我们要初始化第一行的值但是那样太麻烦了我们可以多开一行并初始化0这样就不用单独处理第一行了。注意和cost数组的下标对应关系 填表顺序 从上往下每一行从左往右。
5.返回值 依据状态表示假设最后的房子是i号返回值为min({dp[n][0], dp[n][1], dp[n][2]})。
代码实现
class Solution {
public:int minCost(vectorvectorint costs){int n costs.size();//dp[i][j]表示第i号房子粉刷成j颜色的最低花费//其中0表示红色1表示蓝色2表示绿色vectorvectorint dp(n 1, vectorint(3));//空间多开一行并初始化0不用单独处理第一行for (int i 1; i n 1; i){dp[i][0] costs[i - 1][0] min(dp[i - 1][1], dp[i - 1][2]);dp[i][1] costs[i - 1][1] min(dp[i - 1][0], dp[i - 1][2]);dp[i][2] costs[i - 1][2] min(dp[i - 1][0], dp[i - 1][1]);}return min({dp[n][0], dp[n][1], dp[n][2]});//时间复杂度O(N)//空间复杂度O(N)}
};4.删除并获得点数中等
链接删除并获得点数 题目描述 做题步骤 状态表示 状态转移方程 这个题就是变形的“打家劫舍”转移方程一致(1) f[i] g[i - 1] v[ i ] (删除本位置可得点数)(2) g[i] max(g[i - 1], f[i - 1]) 初始化 数组转化完成后dp表不需要处理。 填表顺序 从左往右。 返回值 返回值为max(f[N - 1],g[N - 1])
代码实现
class Solution {
public:int deleteAndEarn(vectorint nums){int n nums.size();//创建数组进行映射//题目中1 nums[i] 10000const int N 10001;int v[N] {0};for(auto val : nums)v[val] val;//“打家劫舍”vectorint f(N); //f[i]表示以i区域为结尾并且删除本区域的最大点数auto g f; //g[i]表示以i区域为结尾但不删除本区域的最大点数for (int i 1; i N; i){f[i] g[i - 1] v[i];g[i] max(f[i - 1], g[i - 1]);}return max(f[N - 1],g[N - 1]);//时间复杂度O(N)//空间复杂度O(1)}
};//上面的写法简洁一些但无论数据量多少都会遍历10000次
//可以记录数组的最大、最小值来加快速度
// class Solution {
// public:
// int deleteAndEarn(vectorint nums)
// {
// int n nums.size();
// vectorint v(10001);
// //先遍历一次
// int _max nums[0];
// int _min nums[0];
// for (int i 0; i n; i)
// {
// v[nums[i]] nums[i];
// _max max(_max, nums[i]);
// _min min(_min, nums[i]);
// }// vectorint f(10001);
// auto g f;
// for (int i _min; i _max; i)
// {
// f[i] g[i - 1] v[i];
// g[i] max(f[i - 1], g[i - 1]);
// }// return max(f[_max],g[_max]);
// }
// };5.买卖股票的最佳时期含⼿续费中等
链接买卖股票的最佳时期含⼿续费 题目描述 做题步骤
状态表示
dp[i][j]第i天结束时处于j状态的最大利润。 状态转移方程0表示结束有股票1表示结束没有股票fee是手续费prices[i]表示第i天的股票价格 (1)dp[i][0] max(dp[i - 1][0], dp[i - 1][1] - prices[i]) (2)dp[i][1] max(dp[i - 1][1], dp[i - 1][0] prices[i] - fee) 初始化 初始化第0天状态即可dp[0][0] - prices[0];。 填表顺序 从上到下。 返回值 返回值为max(dp[n - 1][1], dp[n - 1][0])。
代码实现
class Solution {
public:int maxProfit(vectorint prices, int fee) {int n prices.size();//dp[i][j]:第i天结束处于j状态的最大利润vectorvectorint dp(n, vectorint(2));//这种解法买入还是卖出交手续费都一样(反正买入了一定会卖出)dp[0][0] - prices[0];for(int i 1; i n; i){dp[i][0] max(dp[i - 1][0], dp[i - 1][1] - prices[i]);dp[i][1] max(dp[i - 1][1], dp[i - 1][0] prices[i] - fee);}return max(dp[n - 1][1], dp[n - 1][0]);//时间复杂度O(N)//空间复杂度O(N)}
};6.买卖股票的最佳时机含冷冻期中等
链接买卖股票的最佳时机含冷冻期 题目描述 做题步骤 状态表示 状态转移方程 0是买入有股票、1是可交易、2是冷冻prices[i]表示第i天的股票价格状态转移方程为 (1)dp[i][0] max(dp[i - 1][1] - prices[i], dp[i - 1][0]) (2)dp[i][1] max(dp[i - 1][2], dp[i - 1][1]) (3)dp[i][2] dp[i - 1][0] prices[i] 初始化 当前天的三种状态需要前一天的状态所以初始化dp表的第一行 dp[0][0]想该天结束后处于买入状态必须把股票买了dp[0][0] -prices[i] dp[0][1]什么都不干dp[0][1] 0 dp[0][2]想该天结束处于冷冻在同一天买入和卖出dp[0][2] 0 填表顺序 从上到下。 返回值 最大值应该手中没有股票假设数组有n个元素最大值为max(dp[n - 1][1], dp[n - 1][ 2 ])。
代码实现
class Solution {
public:int maxProfit(vectorint prices) {int n prices.size();//dp[i][j]第i天结束后处于j状态时的最大利润vectorvectorint dp(n, vectorint(3));//初始化dp[0][0] - prices[0];for(int i 1; i n; i){dp[i][0] max(dp[i - 1][1] - prices[i], dp[i - 1][0]);dp[i][1] max(dp[i - 1][2], dp[i - 1][1]);dp[i][2] dp[i - 1][0] prices[i];}return max(dp[n - 1][2],dp[n - 1][1]);}
};7.买卖股票的最佳时机III困难
链接买卖股票的最佳时机III 题目描述 做题步骤 状态表示 状态转移方程 由前面的分析可知状态转移方程为 (1)f[i][j] max(f[i - 1][j], g[i - 1][j] - prices[i]) (2)if(j 1) g[i][j] max(g[i - 1][j], f[i - 1][j - 1] prices[i]) else g[i][j] g[i - 1][j] 初始化 需要i 0的状态初始化第一行。 (1)处于第一行的时候只有f[0][0]和g[0][0]存在f[0][0] -prices[0]g[0][0] 0。 (2)为了避免不存在的状态干扰取max值我们把不存在的状态统一初始化为 INT_MIN / 2。INT_MIN会越界尽可能小就行 填表顺序 从上往下填每一列从左往右填每一行。 返回值 返回最后一行的最大值即可。
代码实现
class Solution {
public://可能会越界,取INT_MIN的一半const int INF INT_MIN / 2;int maxProfit(vectorint prices) {int n prices.size();//dp[i][j]表示在第i天结束后完成j次交易处于状态下的最大利润vectorvectorint f(n, vectorint(3, INF)); //买入auto g f; //可交易//初始化f[0][0] -prices[0];g[0][0] 0;for (int i 1; i n; i){for(int j 0; j 3; j){f[i][j] max(f[i - 1][j], g[i - 1][j] - prices[i]);g[i][j] g[i - 1][j];//j 0的时候前置状态f[i - 1][j - 1]不存在if(j 1)g[i][j] max(g[i][j], f[i - 1][j - 1] prices[i]);} }return max({g[n - 1][0], g[n - 1][1], g[n - 1][2]});}
};8.买卖股票的最佳时机IV困难
这个题目的思考方式和第7题完全一致大家可以先自己试着做一下。 链接买卖股票的最佳时机IV
代码实现
class Solution {
public:const int INF INT_MIN / 2;int maxProfit(int k, vectorint prices) { int n prices.size();//n天最多完成n / 2次交易k不能超过这个值k min(k, n / 2);//买入//dp[i][j]表示在第i天结束后完成j次交易处于状态下的最大利润vectorvectorint f(n, vectorint(k 1, INF));//卖出auto g f;//初始化(先买再说)f[0][0] -prices[0];g[0][0] 0;for (int i 1; i n; i){for(int j 0; j k; j){f[i][j] max(f[i - 1][j], g[i - 1][j] - prices[i]);g[i][j] g[i - 1][j];if(j 1)g[i][j] max(g[i][j], f[i - 1][j - 1] prices[i]);} }int ret g[n - 1][0];//把利润最大的那个找出来for(int j 1; j k; j){ret max(ret, g[n - 1][j]);}return ret;}
};
