郑州新感觉会所网站哪里做的,响应式网站一般做几个设计稿,网站建设公司业务,展示照片的网站动态规划1.0 动态规划 - - - 斐波那契数列模型1. 第 N 个泰波那契数2. 三步问题3. 使用最小花费爬楼梯4. 解码方法 动态规划 - - - 斐波那契数列模型
1. 第 N 个泰波那契数
题目链接 - Leetcode -1137. 第 N 个泰波那契数
Leetcode -1137. 第 N 个泰波那契数
题目… 动态规划1.0 动态规划 - - - 斐波那契数列模型1. 第 N 个泰波那契数2. 三步问题3. 使用最小花费爬楼梯4. 解码方法 动态规划 - - - 斐波那契数列模型
1. 第 N 个泰波那契数
题目链接 - Leetcode -1137. 第 N 个泰波那契数
Leetcode -1137. 第 N 个泰波那契数
题目泰波那契序列 Tn 定义如下 T0 0, T1 1, T2 1, 且在 n 0 的条件下 Tn 3 Tn Tn 1 Tn 2 给你整数 n请返回第 n 个泰波那契数 Tn 的值。
示例 1 输入n 4 输出4 解释 T_3 0 1 1 2 T_4 1 1 2 4
示例 2 输入n 25 输出1389537
提示 0 n 37 答案保证是一个 32 位整数即 answer 2 ^ 31 - 1。
思路
状态表示这道题可以「根据题目的要求」直接定义出状态表示dp[i] 表示第 i 个泰波那契数的值。状态转移方程dp[i] dp[i - 1] dp[i - 2] dp[i - 3]初始化从我们的递推公式可以看出 dp[i] 在 i 0 以及 i 1 的时候是没有办法进行推导的因为 dp[-2] 或 dp[-1] 不是一个有效的数据。因此我们需要在填表之前将 0, 1, 2 位置的值初始化。题目中已经告诉我们 dp[0] 0, dp[1] dp[2] 1 。填表顺序从左往右返回值应该返回 dp[n] 的值。
代码如下 class Solution {public:int tribonacci(int n){if (n 0 || n 1) return n;// 动态规划当前位置的值等于前三个位置的值相加vectorint dp(n 1);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. 三步问题
题目链接 - Leetcode -面试题 08.01.三步问题
Leetcode -面试题 08.01.三步问题
题目三步问题。有个小孩正在上楼梯楼梯有n阶台阶小孩一次可以上1阶、2阶或3阶。 实现一种方法计算小孩有多少种上楼梯的方式。结果可能很大你需要对结果模1000000007。
示例1 : 输入n 3 输出4 说明 : 有四种走法
示例2 : 输入n 5 输出13
提示 :
n范围在[1, 1000000]之间
思路 状态表示dp[i] 表示到达 i 位置时一共有多少种方法。 状态转移方程 以 i 位置状态的最近的⼀步来分情况讨论 如果 dp[i] 表示小孩上第 i 阶楼梯的所有方式那么它应该等于所有上一步的方式之和 i. 上一步上一级台阶 dp[i] dp[i - 1] ii. 上一步上两级台阶 dp[i] dp[i - 2] iii. 上一步上三级台阶 dp[i] dp[i - 3] 综上所述 dp[i] dp[i - 1] dp[i - 2] dp[i - 3] 初始化从我们的递推公式可以看出 dp[i] 在 i 0, i 1 以及 i 2 的时候是没有办法进行推导的因为 dp[-3] dp[-2] 或 dp[-1] 不是⼀个有效的数据。因此我们需要在填表之前将 1, 2, 3 位置的值初始化。根据题意 dp[1] 1, dp[2] 2, dp[3] 4 。 填表顺序从左往右 返回值应该返回 dp[n] 的值。
代码如下 class Solution {public:int waysToStep(int n){if (n 1 || n 2) return n;vectorint dp(n 1);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];}};3. 使用最小花费爬楼梯
题目链接 - Leetcode -746.使用最小花费爬楼梯
Leetcode -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 10000 cost[i] 999
思路
状态表示dp[i] 表示到达 i 位置时的最小花费。注意到达 i 位置的时候i 位置的钱不需要算上状态转移方程根据最近的一步分情况讨论
先到达 i - 1 的位置然后支付 cost[i - 1] 接下来走一步走到 i 位置dp[i - 1] csot[i - 1] 先到达 i - 2 的位置然后⽀付 cost[i - 2] 接下来走一步走到 i 位置dp[i - 2] csot[i - 2] 。
初始化从我们的递推公式可以看出我们需要先初始化 i 0 以及 i 1 位置的值。容易得到 dp[0] dp[1] 0 因为不需要任何花费就可以直接站在第 0 层和第 1 层上。填表顺序根据「状态转移方程」可得遍历的顺序是「从左往右」。返回值根据「状态表示以及题目要求」需要返回 dp[n] 位置的值。
代码如下 class Solution {public:int minCostClimbingStairs(vectorint cost){int n cost.size();// 从第三个阶梯开始当前阶梯往上爬的费用等于前两个费用的较小值加上爬当前阶梯需要的费用for (int i 2; i n; i)cost[i] min(cost[i - 1], cost[i - 2]) cost[i];// 最后返回最后倒数第一个和第二个阶梯的最小值return min(cost[n - 1], cost[n - 2]);}};4. 解码方法
题目链接 - Leetcode -91.解码方法
Leetcode -91.解码方法
题目一条包含字母 A - Z 的消息通过以下映射进行了 编码
‘A’ - “1” ‘B’ - “2” … ‘Z’ - “26”
要解码已编码的消息所有数字必须基于上述映射的方法反向映射回字母可能有多种方法。例如“11106” 可以映射为
“AAJF” 将消息分组为(1 1 10 6) “KJF” 将消息分组为(11 10 6) 注意消息不能分组为(1 11 06) 因为 “06” 不能映射为 “F” 这是由于 “6” 和 “06” 在映射中并不等价。
给你一个只含数字的 非空 字符串 s 请计算并返回 解码 方法的 总数 。 题目数据保证答案肯定是一个 32 位 的整数。
示例 1 输入s “12” 输出2 解释它可以解码为 “AB”1 2或者 “L”12。
示例 2 输入s “226” 输出3 解释它可以解码为 “BZ” (2 26), “VF” (22 6), 或者 “BBF” (2 2 6) 。
示例 3 输入s “06” 输出0 解释“06” 无法映射到 “F” 因为存在前导零“6” 和 “06” 并不等价。
提示
1 s.length 100s 只包含数字并且可能包含前导零。
思路
状态表示根据上题的经验对于大多数线性 dp 我们经验上都是「以某个位置结束或者开始」做文章这里我们继续尝试「用 i 位置为结尾」结合「题目要求」来定义状态表示。 dp[i] 表示字符串中 [0i] 区间上一共有多少种编码方法状态转移方程定义好状态表示我们就可以分析 i 位置的 dp 值关于 i 位置的编码状况我们可以分为下面两种情况 i. 让 i 位置上的数单独解码成⼀个字母 ii. 让 i 位置上的数与 i - 1 位置上的数结合解码成一个字母。 下面我们就上面的两种解码情况继续分析
让 i 位置上的数单独解码成一个字母就存在「解码成功」和「解码失败」两种情况 i. 解码成功当 i 位置上的数在 [1, 9] 之间的时候说明 i 位置上的数是可以单独解码的那么此时 [0, i] 区间上的解码方法应该等于 [0, i - 1] 区间上的解码方法。因为 [0, i - 1] 区间上的所有解码结果后面填上⼀个 i 位置解码后的字母就可以了。此时 dp[i] dp[i - 1] ii. 解码失败当 i 位置上的数是 0 的时候说明 i 位置上的数是不能单独解码的那么此时 [0, i] 区间上不存在解码方法。因为 i 位置如果单独参与解码但是解码失败了那么前面做的就全部白费了。此时 dp[i] 0 。让 i 位置上的数与 i - 1 位置上的数结合在⼀起解码成一个字母也存在「解码成功」和「解码失败」两种情况 i. 解码成功当结合的数在 [10, 26] 之间的时候说明 [i - 1, i] 两个位置是可以解码成功的那么此时 [0, i] 区间上的解码方法应该等于 [0, i - 2 ] 区间上的解码方法原因同上。此时 dp[i] dp[i - 2] ii. 解码失败当结合的数在 [0, 9] 和 [27 , 99] 之间的时候说明两个位置结合后解码失败这里⼀定要注意 00 01 02 03 04 … 这几种情况那么此时 [0, i] 区间上的解码方法就不存在了原因依旧同上。此时 dp[i] 0 。
综上所述 dp[i] 最终的结果应该是上面四种情况下解码成功的两种的累加和因为我们关心的是解码方法既然解码失败就不用加入到最终结果中去因此可以得到状态转移方程 dp[i] 默认初始化为 0
当 s[i] 上的数在 [1, 9] 区间上时 dp[i] dp[i - 1] 当 s[i - 1] 与 s[i] 上的数结合后在 [10, 26] 之间的时候 dp[i] dp[i - 2]
如果上述两个判断都不成立说明没有解码方法 dp[i] 就是默认值 0 . 初始化可以在最前面加上一个辅助结点帮助我们初始化。使用这种技巧要注意两个点 i. 辅助结点里面的值要保证后续填表是正确的 ii. 下标的映射关系 填表顺序「从左往右」 返回值应该返回 dp[n - 1] 的值表示在 [0, n - 1] 区间上的编码方法。
代码如下 class Solution {public:int numDecodings(string s){int n s.size();// 创建一个 dp 表多开一个空间即添加辅助位置初始化vectorint dp(n 1);dp[0] 1; // 因为前面的初始化会影响后面的填表所以此处应该初始化为1// 只要第一个字符不是 0那么当前位置的解码数就是1if (s[0] ! 0) dp[1] 1;// 开始填表for (int i 2; i n; i){// 单独自己一个数编码dp表的下标与原字符串的下标偏移量为1因为dp表多开了一个空间if (s[i - 1] 1 s[i - 1] 9){dp[i] dp[i - 1];}// 和前一个数联合起来编码int tmp (s[i - 2] - 0) * 10 (s[i - 1] - 0);if (tmp 10 tmp 26){dp[i] dp[i - 2];}}return dp[n];}};
