seo咨询顾问,河源市seo推广,贵州省住房及城乡建设部网站,图库网站源码目录
动态规划dp算法原理
力扣1137. 第 N 个泰波那契数
解析代码1
解析代码2 动态规划dp算法原理 动态规划#xff08;Dynamic Programming#xff09;算法的核心思想是#xff1a;将大问题划分为小问题进行解决#xff0c;从而一步步获取最优解的处理算法 动态规划算法…目录
动态规划dp算法原理
力扣1137. 第 N 个泰波那契数
解析代码1
解析代码2 动态规划dp算法原理 动态规划Dynamic Programming算法的核心思想是将大问题划分为小问题进行解决从而一步步获取最优解的处理算法 动态规划算法与分治算法类似其基本思想也是将待求解问题分解成若干个子问题先求解子问题然后从这些子问题的解得到原问题的解。 与分治法不同的是适合于用动态规划求解的问题经分解得到的子问题往往不是互相独立的即下一个子阶段的求解是建立在上一个子阶段的解的基础上。
除此斐波那契dp外还有其它类型的dp在后面会更新。
动态规划算法解决问题的分类 计数 有多少种方式走到右下角 / 有多少种方法选出k个数使得和是sum 求最大值/最小值 从左上角走到右下角路径的最大数字和最长上升子序列长度 求存在性 取石子游戏,先手是否必胜 / 能不能取出k 个数字使得和是 sum
动态规划dp算法一般步骤
确定状态表示dp[ i ] 表示什么一般以 i 位置为起点或结尾分析化成子问题状态转移方程斐波那契数列的状态转移方程为dp[i] dp[i-1] dp[i-2]初始化斐波那契数列初始化可以为dp[0] 0, dp[1] 1;填表顺序斐波那契数列从左往右填返回值如果斐波那契数列要求是第 n 个斐波那契数返回dp[ n ] 即可 力扣1137. 第 N 个泰波那契数
1137. 第 N 个泰波那契数
难度 简单
泰波那契序列 Tn 定义如下
T0 0, T1 1, T2 1, 且在 n 0 的条件下 Tn3 Tn Tn1 Tn2
给你整数 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。
class Solution {
public:int tribonacci(int n) {}
}; 解析代码1
简单的DP根据题目已经得到状态转移方程了
class Solution {
public:int tribonacci(int n) {if(n 1) // 处理边界return n;vectorint dp(n1, 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进行空间上的优化后面类似的空间优化就不写了因为笔试没用面试能讲出来就行。
class Solution {
public:int tribonacci(int n) {if(n 1) // 处理边界return n;int a 0, b 1, c 1, d 1; // 滚动数组思想优化空间for(int i 3; i n; i){d a b c;a b;b c;c d;}return d;}
};
