代码随想录算法训练营第三十一天 | leetcode：斐波那契数,爬楼梯,使用最小花费爬楼梯
55 / 0 / 创建于 4个月前
_zzh 的个人博客
动态规划理论基础
动态规划题型
什么是动态规划
- 动态规划，英文：Dynamic Programming，简称DP。动态规划中每一个状态一定是由上一个状态推导出来的，这一点就区分于贪心，贪心没有状态推导，而是从局部直接选最优的。
- 动态规划解题步骤
- 确定dp数组（dp table）以及下标的含义
- 确定递推公式
- dp数组如何初始化
- 确定遍历顺序
- 举例推导dp数组
509. 斐波那契数
解题方法
根据题目给出的递推公式：F(n) = F(n - 1) + F(n - 2)可得，第0个斐波那契数是0，第1个斐波那契数是1，第2个是1，第3个是3，第4个是4，第5个….. 用更浅显的语言表达就是当前位置的数等于前两个数相加。
- 第一步确定dp数组的含义：dp[i] 代表第i个斐波那契数
- 递推公式：：F(n) = F(n - 1) + F(n - 2) 其中 n > 1
- 初始化dp数组：$dp[0] = 0; $dp[1] = 1; $dp[$i] = $dp[$i-1] + $dp[$i - 2];
- 遍历顺序：因为当前位置的斐波那契数依赖于前两个数，所以遍历顺序是从前往后。
- 举例推导dp数组：代入 i ,打印dp数组，验证是否符合要求
code
动态规划常规解法
class Solution {
/**
* @param Integer $n
* @return Integer
*/
function fib($n) {
//dp[i] 代表第i个斐波那契数
//题目已给出递推公式：F(n) = F(n - 1) + F(n - 2) 其中 n > 1
if($n < 2) return $n;
//初始化dp数组
$dp[0] = 0; $dp[1] = 1;
//遍历
for($i = 2; $i <= $n; $i++){
$dp[$i] = $dp[$i-1] + $dp[$i - 2];
}
return $dp[$n];
}
}复杂度
时间复杂度
O(n)
空间复杂度
O(n)
动态规划节省空间解法
class Solution {
/**
* @param Integer $n
* @return Integer
*/
function fib($n) {
if($n < 2) return $n;
$a = 0; $b = 1;
for($i = 2; $i <= $n; $i++){
$sum = $a + $b;
$a = $b;
$b = $sum;
}
return $b;
}
}复杂度
时间复杂度
O(n)
空间复杂度
O(1)
递归解法（耗时最久）
class Solution {
/**
* @param Integer $n
* @return Integer
*/
function fib($n) {
if($n < 2) return $n;
return $this->fib($n-1) + $this->fib($n - 2);
}
}复杂度
时间复杂度
O(2^n)
空间复杂度
O(n)，算上了编程语言中实现递归的系统栈所占空间
70. 爬楼梯
解题方法
把前5个阶梯的爬法列出来，就可以得到推导公式n = (n-1) + (n-2)；但是这里和斐波那契题解不一样的地方是这里不需要考虑n = 0的情况，因为1 <= n <= 45。
- 第一步确定dp数组的含义：dp[i] 代表到第 i 个阶梯，一共有dp[i]种爬法。
- 递推公式：F(n) = F(n - 1) + F(n - 2) 其中 n > 2
- 初始化dp数组：$dp[1] = 1; $dp[2] = 2; $dp[$i] = $dp[$i-1] + $dp[$i - 2];
- 遍历顺序：因为当前位置的爬法依赖于前两个种，所以遍历顺序是从前往后。
- 举例推导dp数组：代入 i ,打印dp数组，验证是否符合要求
code
动态规划常规解法
class Solution {
/**
* @param Integer $n
* @return Integer
*/
function climbStairs($n) {
//把前5个阶梯的爬法列出来，就可以得到推导公式n = (n-1) + (n-2)
if($n < 3) return $n;
$dp[1] = 1; $dp[2] = 2;
for($i = 3; $i <= $n; $i++){
$dp[$i] = $dp[$i-1] + $dp[$i-2];
}
//print_r($dp);
return $dp[$n];
}
}复杂度
时间复杂度
O(n)
空间复杂度
O(n)
动态规划节省空间解法
class Solution {
/**
* @param Integer $n
* @return Integer
*/
function climbStairs($n) {
if($n < 3) return $n;
$a = 1; $b = 2;
for($i = 3; $i <= $n; $i++){
$sum = $a + $b;
$a = $b;
$b = $sum;
}
return $b;
}
}复杂度
时间复杂度
O(n)
空间复杂度
O(1)
746. 使用最小花费爬楼梯
解题方法
根据题意我们可以从第0个阶梯或者第1个阶梯开始，那么$dp[0] = 0，$dp[1] = 0。因为在当前位置没有移动，不花费体力。从 下标 0 下标1 开始跳就要花费体力了。可以有两个途径得到dp[i]，一个是dp[i-1] 一个是dp[i-2]。而题目要求最小，则取最小值即可。
- dp[i - 1] 跳到 dp[i] 需要花费 dp[i - 1] + cost[i - 1]。
- dp[i - 2] 跳到 dp[i] 需要花费 dp[i - 2] + cost[i - 2]。
- 第一步确定dp数组的含义：到达第i台阶所花费的最少体力为dp[i]。
- 递推公式：$dp[$i] = min($dp[$i-1] + $cost[$i-1],$dp[$i-2] + $cost[$i-2]); 其中 n > 1
- 初始化dp数组：$dp[0] = 0; $dp[1] = 0; $dp[$i] = min($dp[$i-1] + $cost[$i-1],$dp[$i-2] + $cost[$i-2]);
- 遍历顺序：因为当前位置的爬法依赖于前两个种，所以遍历顺序是从前往后。
- 举例推导dp数组：代入 i ,打印dp数组，验证是否符合要求
code
动态规划常规解法
class Solution {
/**
* @param Integer[] $cost
* @return Integer
*/
function minCostClimbingStairs($cost) {
$dp[0] = $dp[1] = 0;
for($i = 2; $i <= count($cost); $i++){
$dp[$i] = min($dp[$i-1] + $cost[$i-1],$dp[$i-2] + $cost[$i-2]);
}
return end($dp);
}
}复杂度
时间复杂度
O(n)
空间复杂度
O(n)
动态规划节省空间解法
class Solution {
/**
* @param Integer[] $cost
* @return Integer
*/
function minCostClimbingStairs($cost) {
$dp0 = $dp1 = 0;
for($i = 2; $i <= count($cost); $i++){
$min = min($dp1 + $cost[$i-1],$dp0 + $cost[$i-2]);;
$dp0 = $dp1;
$dp1 = $min;
}
return $dp1;
}
}复杂度
时间复杂度
O(n)
空间复杂度
O(1)
本作品采用《CC 协议》，转载必须注明作者和本文链接
关于 LearnKu
粤公网安备 44030502004330号
推荐文章：