音乐网站网页设计,域名除了做网站还能做什么,广州有哪几个区,商标代理公司动态规划
动态规划的思路一共有五个步骤#xff1a;
状态表示#xff1a;由经验和题目要求得出#xff0c;这个确实有点抽象#xff0c;下面的题目会带大家慢慢感受状态标识状态转移方程初始化#xff1a;避免越界访问 dp 表#xff0c;所以在进行填表之前我们要预先填…动态规划
动态规划的思路一共有五个步骤
状态表示由经验和题目要求得出这个确实有点抽象下面的题目会带大家慢慢感受状态标识状态转移方程初始化避免越界访问 dp 表所以在进行填表之前我们要预先填写好一些数据。填表顺序返回值
动态规划的代码书写步骤 建表初始化填表返回值最后中间可能由细节的处理
实战演练
第N个泰波那契数 解析对于一维的数据我们的状态表示基本是题目要求什么状态表示就是什么上面这个题目要求我们求出第N 个泰波那契数那么我们的 dp 表就定义为 dp[i] 表示 第 i 个 泰波那契数。
状态转移方程题目已经很贴心告诉我们 T(n 3) T(n) T(n1) T(n2)我们稍微转化一下T(n) T(n-3) T(n-2) T(n-1)即 dp[i] dp[i-1] dp[i-2] dp[i-3]
初始化我们在求 dp[0]、dp[1]、dp[2] 的时候是不能直接使用状态转移方程来求取的否则就会发生数组越界所以我们要在填表之前把着三个 dp 值给预设好dp[0] 0, dp[1] dp[2] 1
填表顺序由于在初始化我们已经填好了前面三个数字dp[0]、dp[1]、dp[2]所以我们从 i 3 开始填表从左向右这个顺序把 dp 表填满。
返回值题目要求我们求 第N 个泰波那契数正好我们的 dp 表的状态表示也是这个所以直接返回 dp[n] .
细节处理如果 n 0 / 1 的时候直接返回不需要初始化和填表了避免数组访问越界举个例子假设 n 等于 0也就是说 dp 表其实就只有一个位置但是你初始化要初始三个位置数组妥妥越界访问。
class Solution {public int tribonacci(int n) {//建表int[] dp new int[n 1];//细节处理if(n 0 || n 1) return n;//初始化dp[0] 0; dp[1] 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];}
}三步问题 解析 状态表示一维数组形式我们通常以题目要求出来思考状态表示如果这个状态表示不能推导出状态转移方程那就再换别的状态表示这里我们直接定义状态表示为 dp[i] 表示上到第 i 个台阶一共有多少中方式。
状态转移方程上到 第 i 个台阶有多少种方式 等于上到第 i - 1 个台阶需要多少种方式 上到第 i - 2 个台阶需要多少种方式 上到第 i - 3 个台阶需要多少种方式为什么是三种台阶方式相加回到题目一次可以跨一步 / 两步 / 三步。
初始化我们需要将 dp[1] 1 dp[2] 2dp[3] 4设置好同样这里也有细节要处理如果 n 1 或者 n 2 直接返回即可。
填表顺序从 i 4 开始填从左到右
返回值直接返回 dp[n]
这道题还有一个小细节就是结果可能很大我们需要将结果 取模 1000000007在每次进行加法的时候都去取模即可。
class Solution {public int waysToStep(int n) {//建表int[] dp new int [n1];//细节处理if(n 1 || n 2) return n;//初始化dp[1] 1; dp[2] 2; dp[3] 4;//填表for(int i 4; i n; i) {dp[i] ((dp[i-1] dp[i-2]) % 1000000007 dp[i-3]) % 1000000007;}//返回值return dp[n]; }
}使用最小花费爬楼梯 解析 状态表示这里还是一个一维形式的数组我们定义 dp[i] 表示达到 第 i 个台阶所需要的最小花费。
状态转移方程由于每次可以走一个或者两个台阶所以我们要推导出 dp[i] 就要知道 dp[i-1] cost[i-1] 和 dp[i-2] cost[i-2] 的最小花费是什么。这个为什么要加上 cost[i-1] / cost[i-2] ? 因为 dp[i] 表示达到 i 台阶需要的最小花费你如果从 i 台阶往上走就需要先支付 i 台阶的费用也就是 cost[i]。
初始化dp[1] 0dp[2] 0由于Java创建数组的时候默认值就是 0所以可以不进行初始化了但是细节还是要处理的如果 n 0 || n 1 直接返回 n。
填表顺序从 i 2 开始从左往右填
返回值dp[n]
class Solution {public int minCostClimbingStairs(int[] cost) {//建表int n cost.length;int[] dp new int[n1];//细节处理if(n 0 || n 1) return n;//填表for(int i 2; i n; i) {dp[i] Math.min(dp[i-1] cost[i-1], dp[i-2] cost[i-2]);}return dp[n];}
}解码方式 解析 状态表示到达第 i 个字符的时候一共有多少种编码。
状态转移方程首先我们先进行单字符解码如果一个字符的数值不等于 0 的时候是可以单独解码的这时候 dp[i] dp[i-1]把前一个字符有多少种解码方式加起来。 然后就是和前一个字符看是否能共同解码首先要求前一个字符不能为 0 其次两个字符组成的数字要小于等于 26如果都满足说明可以和前一个字符进行合并解码dp[i] dp[i-2]把前前一个字符的解码方式相加起来。
初始化先处理前两个字符的 dp 值并且有一个细节如果 字符串长度为 1 是不能进行第二个字符的解码的需要直接返回。
填表顺序从 i 2 开始从左往右填写。
返回值dp[n-1]
还有一个细节如果一个dp 值为 0 的时候不需要进行后面的填表操作此时已经无法对字符串进行解码了直接返回 0 即可。
class Solution {public int numDecodings(String ss) {//建表int n ss.length();int[] dp new int [n];char[] s ss.toCharArray();//细节处理与初始化if(s[0] - 0 ! 0) {dp[0] 1;} else {dp[0] 0;}if(n 1 || dp[0] 0) {return dp[0];}//处理第二个字符if(s[1] - 0 ! 0) dp[1];if(s[0] - 0 ! 0 (s[0] - 0) * 10 (s[1] - 0) 26) dp[1];//填表for(int i 2; i n; i) {if(s[i] - 0 ! 0) dp[i] dp[i-1];if(s[i-1] - 0 ! 0 10 * (s[i-1] - 0) (s[i] - 0) 26) dp[i] dp[i-2];if(dp[i] 0) return 0;}return dp[n-1];}
}小结
面对一维形式的数据的时候一般我们的状态表示直接从题目要求中获取。 在初始化之前一定要注意没有细节需要处理。
