做暧暧的网站,平面设计基础学什么,郴州新网交友信息,想自己做网站吗代码随想录算法训练营第38天 | 509. 斐波那契数、70. 爬楼梯、746. 使用最小花费爬楼梯 理论基础自己看到题目的第一想法看完代码随想录之后的想法 链接: 509. 斐波那契数 链接: 70. 爬楼梯 链接: 746. 使用最小花费爬楼梯
理论基础
五部曲#xff1a; 1.确定dp数组#xf… 代码随想录算法训练营第38天 | 509. 斐波那契数、70. 爬楼梯、746. 使用最小花费爬楼梯 理论基础自己看到题目的第一想法看完代码随想录之后的想法 链接: 509. 斐波那契数 链接: 70. 爬楼梯 链接: 746. 使用最小花费爬楼梯
理论基础
五部曲 1.确定dp数组dp table以及下标的含义 2.确定递推公式 3.dp数组如何初始化 4.确定遍历顺序 5.举例推导dp数组
自己看到题目的第一想法
509.斐波那契数直接看题解。 70.爬楼梯 746.使用最小花费爬楼梯
看完代码随想录之后的想法
509.斐波那契数 五部曲上秤 1确定dp数组以及下标的含义dp[i]的定义为第i个数的斐波那契数值是dp[i] 2确定递推公式直接有递推公式状态转移方程dp[i]dp[i-1]dp[i-2] 3dp数组如何初始化dp数组的初始化题目给了dp[0]0dp[1]1 4确定遍历顺序从递归公式可以看出dp[i]依赖dp[i-1]和dp[i-2]那么遍历顺序应当先确定前面的数再确定后面的数所以是从前到后遍历。 5举例推导dp数组根据递推公式推导举例如果发现结果不对就把dp数组打印出来看看推导的数列是否一致。 代码还是很简单的可以使用 70.爬楼梯 五部曲上秤 1确定dp数组以及下标的含义dp[i]的定义为爬到第i层楼有dp[i]种方法 2递推公式dp[i]有两个方向可以推出来dp[i-1]和dp[i-2]这里理解是一个难点为什么可以这样推导因为只能走1步或者2步而没有其他方法上一步到这一步。所以dp[i]dp[i-1]dp[i-2]。 3dp数组如何初始化dp[1]1,dp[2]2 4确定遍历顺序从前向后遍历 5举例推导如果代码有问题就把dp数组打印出来看与自己的举例是否一样。 746.使用最小花费爬楼梯 五部曲上秤 1确定dp数组以及下标的含义dp[i]的定义为到位置i所需要的花费是多少。 2递推公式有两个途径得到dp[i]一个是dp[i-1]一个是dp[i-2]有一个难想的点就是究竟是从dp[i-1]跳还是从dp[i-2]跳呢根据题意是需要最小的那么就是dp[i]min[dp[i-1]cost[i-1],dp[i-2]cost[i-2])。 3如何初始化dp[0]0, dp[1]0 4遍历顺序从前向后遍历 5举例推导
