摄影师如何做网站,网站建设 网站优化营销型网站建设专家,成都医疗网站建设,网站开发慕枫目录
认识动态规划
LeetCodeOJ练习
斐波那契数列模型 认识动态规划 1.动态规划是一种用于解决优化问题的算法策略。 2.它的核心原理是把一个复杂的问题分解为一系列相互关联的子问题。通过先求解子问题#xff0c;并且记录这些子问题的解#xff08;通常用一个表格之类的…目录
认识动态规划
LeetCodeOJ练习
斐波那契数列模型 认识动态规划 1.动态规划是一种用于解决优化问题的算法策略。 2.它的核心原理是把一个复杂的问题分解为一系列相互关联的子问题。通过先求解子问题并且记录这些子问题的解通常用一个表格之类的存储结构避免重复计算然后基于这些子问题的解来构建原问题的解 3.解题步骤
这里通过一道题进行说明一些概念
传送门:LeetCode1137 第 N 个泰波那契数 1.创建一个dp表(一般用数组) 2.确定状态表示 状态表示的话简单理解就是dp表里面的值所代表的含义 对于此题的话就是dp[i]表示的含义为第i个泰波那契数 该如何确定状态表示: (1)可以根据题目要求对于本题就是 (2)经验和题目要求 (3)分析问题的过程中发现重复子问题 3.确定状态转移方程 简单说就是求出dp[i]等于什么 对于本题就是dp[i]dp[i-1]dp[i-2]dp[i-3] 4.初始化 确定初始状态的值保证填表时不发生越界 对于此题就是dp[0],dp[1],dp[2]必须初始化若通过状态转移方程计算的话就会发生越界 5.填表顺序 确定是从左向右还是从右向左的顺序填表确保填写当前状态的时候所需要的状态已经计算过了对于本题就是从左向右的顺序 6.返回结果 根据题目要求和具体的状态表示对于此题就是返回dp[n] 7.空间优化(不是必须) 因为创建dp表导致空间复杂度为O(N),在这里我们可以用滚动数组进行优化 通过几个变量来降低空间复杂度 当我们依次往后求dp[i]时前面的一些状态可以舍去仅仅用中间若干个有效的状态比如求dp[5]只需要知道dp[4],dp[3],dp[2]就可以了像这样的情况就可以使用滚动数组来优化 本题具体代码
没有做优化的版本
int tribonacci(int n) {//1.创建dp表//2.初始化//3.填表//4.返回值//处理边界情况if(n0) return 0;if(n1 || n2) return 1;vectorint dp(n1);dp[0]0,dp[1]dp[2]1;for(int i3;in;i)dp[i]dp[i-1]dp[i-2]dp[i-3];return dp[n];}
优化的版本
int tribonacci(int n) {//1.创建dp表//2.初始化//3.填表//4.返回值//处理边界情况if(n0) return 0;if(n1 || n2) return 1;int a0,b1,c1,d0;for(int i3;in;i){dabc;ab,bc,cd;//滚动操作}return d;}
LeetCodeOJ练习
斐波那契数列模型
1.面试题08.01 三步问题
画图分析: 使用动态规划解决此题的步骤 1.创建dp表 2.确定状态表示 对于一般题都是集合经验和题目要求来确定 常见的经验有:以i位置为结尾xxx;以i位置为开始xxx 对于本题dp[i]表示到i位置的走法数 3.确定状态转移方程 确定方法一般为:以当前i位置状态最近的一步来划分问题将划分的每个子问题用dp[x]表示 4.初始化防止出现越界 对dp[1],dp[2],dp[3]进行初始化 5.填表顺序 从左往右 6.返回结果 dp[n] 具体代码:注意细节问题要将相加的结果模1e97防止越界
int waysToStep(int n) {//1.创建dp表//2.初始化//3.填表//4.返回值const int MOD1e97;//处理边界防止越界if(n1 || n2) return n;if(n3) return 4;vectorint dp(n1);dp[1]1,dp[2]2,dp[3]4;for(int i4;in;i)dp[i]((dp[i-1]dp[i-2])%MODdp[i-3])%MOD;return dp[n];} 2.LeetCode746 使用最小花费爬楼梯
画图分析: 使用动态规划解决此题的步骤: 1.创建dp表 2.确定状态表示 根据经验题目要求此处的dp[i]可以表示到达i位置时的最下花费 或者dp[i]表示从i位置开始到顶楼的最小花费 3.确定状态转移方程 (1)dp[i]可以表示到达i位置时的最下花费 对应代码 int minCostClimbingStairs(vectorint cost) {//1.创建dp表//2.初始化//3.填表//4.返回结果int ncost.size();vectorint dp(n1);dp[0]dp[1]0;for(int i2;in;i){dp[i]min(dp[i-1]cost[i-1],dp[i-2]cost[i-2]);}return dp[n];} (2) dp[i]表示从i位置开始到顶楼的最小花费 对应代码: int minCostClimbingStairs(vectorint cost) {int ncost.size();vectorint dp(n);dp[n-1]cost[n-1],dp[n-2]cost[n-2];for(int in-3;i0;--i)dp[i]cost[i]min(dp[i1],dp[i2]);return min(dp[0],dp[1]);}
3.LeetCode91 解码方法 使用动态规划解决此题的步骤 1.创建dp表 2.确定状态表示 方法依旧是根据经验结合题意 dp[i]表示以i位置为结尾解析方法的总数(从开始解析到i位置的方法总数) 3.确定状态转移方程 根据最近的一步划分问题 具体代码为
int numDecodings(string s) {//1.创建dp表//2.初始化//3.填写dp表//4.返回结果int n s.size();vectorint dp(n); // 创建⼀个 dp表// 初始化前两个位置dp[0] s[0] ! 0;if(n 1) return dp[0]; // 处理边界情况if(s[1]!0) dp[1] dp[0];int t (s[0] - 0) * 10 s[1] - 0;if(t 10 t 26) dp[1] 1;for(int i 2; i n; i){// 如果单独编码if(s[i]!0) dp[i] dp[i - 1];// 如果和前⾯的⼀个数联合起来编码int t (s[i - 1] - 0) * 10 s[i] - 0;if(t 10 t 26) dp[i] dp[i - 2];}// 返回结果return dp[n - 1];}
对于上述代码我们会发现初始化操作和填写表操作几乎一致在这里我们就可以对边界问题和初始化问题做优化的
优化的方法为添加虚拟头结点使新dp表和旧dp表产生如下的映射关系 这里有两个需要注意的问题 (1)虚拟节点里面的值要确保后面的填表也是正确的 (2)新旧dp表下标间的映射关系 对于(1)的话新的dp表中对于计算dp[2]dp[1]dp[0],dp[1]是直接映射下来的不用管重点是dp[0]中的值当球dp[2]要用到dp[0]时若原字符串中的第一个和第二个位置字符拼起来能解码成功时说明s[0]也是可以单独解码成功的若dp[0]0的话就会缺失这个能单独解码的情况所以dp[0]1
优化后的代码 int numDecodings(string s) {//1.创建dp表//2.初始化//3.填写dp表//4.返回结果int n s.size();vectorint dp(n1); // 创建⼀个 dp表// 初始化前两个位置dp[0] 1;dp[1]s[1-1]!0;for(int i 2; i n; i){// 如果单独编码if(s[i-1]!0) dp[i] dp[i - 1];// 如果和前⾯的⼀个数联合起来编码int t (s[i - 2] - 0) * 10 s[i-1] - 0;if(t 10 t 26) dp[i] dp[i - 2];}// 返回结果return dp[n];}
