光伏电站建设的国家网站,溧阳建设集团网站,网络培训seo,什么是优化网站动态规划1引言题目509. 斐波那契数70. 爬楼梯746. 使用最小花费爬楼梯小结53. 最大子数组和结语引言
蓝桥杯快开始了啊#xff0c;自从报名后还没认真学过算法有(﹏)′#xff0c;临时抱一下佛脚#xff0c;一起学学算法。
题目
509. 斐波那契数
斐波那契数 自从报名后还没认真学过算法有(﹏)′临时抱一下佛脚一起学学算法。
题目
509. 斐波那契数
斐波那契数 通常用 F(n) 表示形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始后面的每一项数字都是前面两项数字的和。也就是
F(0) 0F(1) 1 F(n) F(n - 1) F(n - 2)其中 n 1 给定 n 请计算 F(n) 。
链接: link 相信这题大家都能闭着眼睛都能写出来了。 这是一个最基础的递推题目 递推公式为**F(n) F(n - 1) F(n - 2)** 1.定义一个数组arr[n1], 用来记录n位置的斐波那契数值 2.定义一个循环变量i 然后进行循环F(i) F(i - 1) F(i - 2) 3.返回arr[n] 代码
int fib(int n){if(n1){return n;}else{int arr[n1];arr[0]0;arr[1]1;for(int i2;in;i){arr[i]arr[i-1]arr[i-2];}return arr[n];}
}70. 爬楼梯
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢 示例 1 输入n 2 输出2 解释有两种方法可以爬到楼顶。 1 阶 1 阶2 阶 链接: 爬楼梯
这道题就是斐波那契数列的简单应用只是在斐波那契数列是套了一层外套 1.当你在n阶楼梯时 2.只能由n-1阶时走一步或者在n-2阶时走两步 3.所以爬到n阶的方法总数等于爬n-1阶时的方法数加上爬到n-2阶的方法数 也就是F(n)F(n-1)F(n-2)状态转移方程
代码
int climbStairs(int n){int arr[46]{1,1};for(int i2;in;i){arr[i]arr[i-1]arr[i-2];}return arr[n];
}746. 使用最小花费爬楼梯
给你一个整数数组 cost 其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用即可选择向上爬一个或者两个台阶。
你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。
请你计算并返回达到楼梯顶部的最低花费。 示例 1 输入cost [10,15,20] 输出15 解释你将从下标为 1 的台阶开始。 支付 15 向上爬两个台阶到达楼梯顶部。 总花费为 15 。 示例 2 输入cost [1,100,1,1,1,100,1,1,100,1] 输出6 解释你将从下标为 0 的台阶开始。 支付 1 向上爬两个台阶到达下标为 2 的台阶。支付 1 向上爬两个台阶到达下标为 4 的台阶。支付 1 向上爬两个台阶到达下标为 6 的台阶。支付 1 向上爬一个台阶到达下标为 7 的台阶。支付 1 向上爬两个台阶到达下标为 9 的台阶。支付 1 向上爬一个台阶到达楼梯顶部。 总花费为 6 。 提示 2 cost.length 1000 0 cost[i] 999 链接: 使用最小花费爬楼梯
这题和之前的爬楼梯很相似只是从求方案数到求最小值。 求解思路 当你在 n 阶楼梯时 只能由 n-1 阶时走一步或者在 n-2 阶时走两步 当选择走 n-1 其花费也是走到 n-1 步时的最小花费加上走这一步的花费 n-2 其花费也是走到 n-2 步时的最小花费加上走这一步的花费 arr[n]值就是两者之间的最小值 定义一个数组arr[1001],用来存储走到n阶楼梯时的最小花费
我们可以得出状态转移方程为 arr[i]min(arr[i-1]cost[i-1],arr[i-2]cost[i-2]) 代码 int min(int a,int b)
{if(ab)return b;return a;
}int minCostClimbingStairs(int* cost, int costSize){int arr[1001]{0,0};for(int i2;icostSize;i){arr[i]min(arr[i-1]cost[i-1],arr[i-2]cost[i-2]); }return arr[costSize];
}小结
从上述三题可以看出动态规划的大致流程 1.设计状态 2.写出状态转移方程 3.设定初始状态 4.执行状态转移 5.返回最终的解 接下来我们在看一个题
53. 最大子数组和
给你一个整数数组 nums 请你找出一个具有最大和的连续子数组子数组最少包含一个元素返回其最大和。
子数组 是数组中的一个连续部分。 示例 1 输入nums [-2,1,-3,4,-1,2,1,-5,4] 输出6 解释连续子数组 [4,-1,2,1] 的和最大为 6 。 示例 2 输入nums [1] 输出1 题解 定义一个dp[100001]数组用于储存以nums[n]为结尾的子数组的和的最大值。
然后根据题意可知dp[n]的值有两种情况 第一种
当dp[n-1]0时表示的是以nums[n-1]结尾的所有子数组的最大值小于0此时dp[n]的值应该是arr[n]的值因为一个数加上一个小于0的数总比原数小。
第二种
当dp[n-1]0时dp[n]的值应该取dp[n-1]和dp[n-1]nums[n]这两数中的最大值
可得状态转移方程为dp[n]max(dp[n-1]nums[n],nums[n]) 设置初始状态 dp[0]arr[0]
代码
int max(int i,int j)
{if(ij)return i;return j;
}int maxSubArray(int* nums, int numsSize){int dp[100001]{};dp[0]nums[0];int maxvalnums[0];for(int n1;nnumsSize;n){dp[n]max(dp[n-1]nums[n],nums[n]);maxvalmax(maxval,dp[n]);}return maxval;
}结语
本期动态规划就到这了 我是Tom-猫 如果觉得有帮助的话记得 一键三连哦ヾ(≧▽≦*)o。
