网站开发会什么软件,搜索自媒体平台,建设网站郑州,网页搜索青骄第二课堂目录
1、动态规划简介
2、算法实战应用【leetcode】
2.1 题一#xff1a;第N个泰波那契数
2.1.1 算法原理
2.1.2 算法代码
2.1.3 空间优化原理——滚动数组
2.1.4 算法代码——空间优化版本
2.2 题二#xff1a;三步问题 2.2.1 算法原理
2.2.2 算法代码
2.3 题二第N个泰波那契数
2.1.1 算法原理
2.1.2 算法代码
2.1.3 空间优化原理——滚动数组
2.1.4 算法代码——空间优化版本
2.2 题二三步问题 2.2.1 算法原理
2.2.2 算法代码
2.3 题二使用最小花费爬楼梯
2.3.1 算法原理【解法一】
2.3.2 算法代码【解法一】
2.3.3 算法原理【解法二】
2.3.4 算法代码【解法二】
2.4 题三解码方法
2.4.1 算法原理
2.4.2 算法代码
2.4.3 初始化技巧
2.4.4 算法代码——初始化技巧使用 1、动态规划简介
动态规划Dynamic Programming, DP是运筹学的一个分支用于求解最优化问题。
在解决问题时每次产生的子问题并不总是新问题有些子问题被反复计算多次。动态规划算法(自底向上)正是利用了这种子问题的重叠性质对每一个子问题只解一次而后将其解保存在一个表格中在以后尽可能多地利用这些子问题的解。
动态规划算法一般包含以下几个主要步骤:
状态表示dp表中的值所表示的含义。一般由 经验题目要求 得出。对于一维的dp表dp[i]通常有这两种表示形式(由经验得出)①以i位置为结尾......②以i位置为起点......而....就是需要结合题目来得出的。状态转移方程就是dp[i]是怎么来的。dp[i]通常由其相邻的其他状态经过公式计算得出状态转移方程就是这个公式。初始化确保在填dp表的过程中不越界。填表顺序为了在填写当前状态的时候所需要的其他相邻状态已经计算得出了。返回值结合题目要求。
在此过程中我认为确定状态表示是最重要的一点而确定状态转移方程是最难的一点。
2、算法实战应用【leetcode】
2.1 题一第N个泰波那契数 . - 力扣LeetCode 2.1.1 算法原理
对于一维dp状态表示通常由 经验题目要求 得出本题很明显表示第i个泰波那契数的值同时状态转移方程题目也是贴心的给出了。
状态表示dp[i]第i个泰波那契数的值状态转移方程dp[i] dp[i-1] dp[i-2] dp[i-3]初始化dp[0] 0; dp[1] dp[2] 1填表顺序从左往右返回值dp[n]
2.1.2 算法代码 class Solution {public int tribonacci(int n) {if(n 0) return 0;if(n 1 || n 2) return 1;int[] dp new int[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];}
} 2.1.3 空间优化原理——滚动数组
实际上我们可以不用创建一个dp数组来存储数值
通过“滚动数组”的方式进行空间优化。
仅仅使用三个变量就可以解题不必再开辟额外的空间。
2.1.4 算法代码——空间优化版本 class Solution {public int tribonacci(int n) {//动态规划 - 空间优化if(n 0) return 0;if(n 1 || n 2) return 1;int a 0, b 1, c 1, d 0;for(int i 3; i n; i) {d a b c;//滚动操作a b;b c;c d;}return d;}
} 2.2 题二三步问题 . - 力扣LeetCode 2.2.1 算法原理
状态表示(经验题目要求)dp[i]到达第i个位置一共有多少种方式状态转移方程要到达i位置可由移动到i-1/i-2/i-3位置的基础上再移动三/二/一步就可到达即dp[i]dp[i-1]dp[i-2]dp[i-3]初始化dp[1]1; dp[2]2; dp[3]4;填表顺序从左往右
2.2.2 算法代码 class Solution {//dp[i]状态表示到达i位置一共有多少种方法public int waysToStep(int n) {//1e9 7double类型int MOD (int)1e9 7;if(n 1 || n 2) return n;int[] dp new int[n 1];//初始化dp[1] 1; dp[2] 2; dp[3] 4;for(int i 4; i n 1; i) {//状态转移方程dp[i] ((dp[i - 1] dp[i - 2]) % MOD dp[i - 3]) % MOD;}return dp[n];}
} 2.3 题二使用最小花费爬楼梯 . - 力扣LeetCode 2.3.1 算法原理【解法一】
状态表示dp[i]到达i位置最小花费的金额(以i位置为结尾)状态转移方程需要考虑到达i-1位置和到达i-2位置最小花费的金额数考虑完后再进一步到达i位置。也就是说dp[i]min(dp[i-1]cost[i-1],dp[i-2]cost[i-2]);初始化dp[0]0; dp[1]0;防越界dp的建表顺序从左至右返回值dp[n]
2.3.2 算法代码【解法一】 class Solution {public int minCostClimbingStairs(int[] cost) {//解法一int n cost.length;//状态表示dp[i]到达i位置时最小花费int[] dp new int[n 1];//初始化dp[0] dp[1] 0;//填表顺序从左往右for(int i 2; i n; i) {//状态转移方程dp[i] Math.min(dp[i - 1] cost[i - 1], dp[i - 2] cost[i - 2]);}//返回值:dp[n]return dp[n];}
} 2.3.3 算法原理【解法二】
状态表示dp[i]从i位置开始到达楼顶最小花费的金额(以i位置为起点)状态转移方程需要考虑i1位置和i2位置到达楼顶最小花费的金额数再选择走一步还是走两步。也就是说dp[i]min(cost[i-1],dp[i-2])cost[i];初始化dp[i-1]cost[i-1]; dp[i-2]cost[i-2];防越界dp的建表顺序从右至左返回值min(dp[0],dp[1])
2.3.4 算法代码【解法二】 class Solution {public int minCostClimbingStairs(int[] cost) {int n cost.length;//状态表示dp[i]以i位置为起点到达楼顶的最小花费int[] dp new int[n];//初始化dp[n - 1] cost[n - 1];dp[n - 2] cost[n - 2];for(int i n - 3; i 0; i--) {//填表顺序 - 从右往左//状态转移方程 -- 自身花费后面俩台阶的最小花费dp[i] cost[i] Math.min(dp[i 1], dp[i 2]);}//返回值考虑 从第一个台阶出发 or 从第二个台阶出发return Math.min(dp[0], dp[1]);}
} 2.4 题三解码方法 . - 力扣LeetCode 2.4.1 算法原理
状态表示dp[i]以i位置为结尾解码方式的总数状态转移方程s[i]单独解码(成功/失败)s[i]/s[i-1]组合解码(成功/失败)dp[i]dp[i-1]dp[i-2];初始化①if(s[0]!0) dp[0]1; ②dp[1] --1. s[1]单独解码 2. s[1]与s[0]组合解码返回值dp[n-1]
2.4.2 算法代码 class Solution {public int numDecodings(String s) {int n s.length();char[] c s.toCharArray();//状态表示dp[i]以i位置为结尾解码方式的总数int[] dp new int[n];//初始化第一个位置if(c[0] ! 0) dp[0];//当长度为1时if(n 1) return dp[0];//初始化第二个位置if(c[0] ! 0 c[1] ! 0) dp[1];//单独编码int t ((c[0] - 0) * 10 (c[1] - 0));if(t 10 t 26) dp[1];//组合编码for(int i 2; i n; i) {//单独编码if(c[i] ! 0) dp[i] dp[i - 1];//组合编码int tt ((c[i - 1] - 0) * 10 (c[i] - 0));if(tt 10 tt 26) dp[i] dp[i - 2];}return dp[n - 1];}
} 2.4.3 初始化技巧
在编写代码时我们发现了一个问题 我们在完成初始化工作时非常的麻烦初始化的代码占据了大量的篇幅此时我们可以使用初始化技巧 --- dp数组在创建时多开辟一个节点。将初始化时的代码放进循环中(将要初始化的节点与普通节点一概而论)在填dp表的时候完成初始化。
不过因为多开辟了一个位置所以在循环填dp表时也需要注意以下问题
与原数组的下标映射关系发生了改变注意虚拟节点的值(多开辟的那一个节点)虚拟节点的值要保证后面计算得到的结果是正确的。
在本题中虚拟节点dp[0]的值应该为1
原因
当s[1]可与s[0]组合解码时会这样计算dp[2]d[2-2](s中的i为1映射到新dp中i为2) 因为能够组合解码所以虚拟节点dp[0]的值应为1
2.4.4 算法代码——初始化技巧使用 class Solution {public int numDecodings(String s) {//初始化技巧 -- 优化int n s.length();char[] c s.toCharArray();//状态表示dp[i 1]以i位置为结尾解码方式的总数int[] dp new int[n 1];//处理虚拟节点里的值dp[0] 1;//初始化第一个位置if(c[0] ! 0) dp[1];for(int i 2; i n 1; i) {//单独编码if(c[i - 1] ! 0) dp[i] dp[i - 1];//组合编码int t ((c[i - 1 - 1] - 0) * 10 (c[i - 1] - 0));if(t 10 t 26) dp[i] dp[i - 2];}return dp[n];}
} END
