Day 38 理论基础 509. 斐波那契数 70. 爬楼梯 746. 使用最小花费爬楼梯

本文主要是介绍Day 38 理论基础 509. 斐波那契数 70. 爬楼梯 746. 使用最小花费爬楼梯，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

动态规划理论基础

概念

动态规划，Dynamic Programming，称dp，如果某一问题有很多重叠子问题，使用动态规划是最有效的。

动态规划中每一个状态一定是由上一个状态推导出来的，这一点就区分于贪心，贪心没有状态推导，而是从局部直接选最优的；

例如：

有N件物品和一个最多能背重量为W的背包；

第i件物品的重量是weight[i]，得到的价值是value[i] ；

每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大；

动态规划中dp[j]是由dp[j-weight[i]]推导出来的，然后取max(dp[j], dp[j - weight[i]] + value[i])；

如果是贪心，每次拿物品选一个最大的或者最小的就完事了，和上一个状态没有关系，所以贪心解决不了动态规划的问题；

解题步骤

递归公式很重要，但是动态规划不止有递归公式；

确定dp数组（dp table）以及下标的含义；
确定递推公式；
dp数组如何初始化；
确定遍历顺序；
举例推导dp数组；

只有每一步都清晰了，才算彻底理解了动态规划

如何debug

做动规的题目，写代码之前一定要把状态转移在dp数组的上具体情况模拟一遍，心中有数，确定最后推出的是想要的结果；

最直接的方法，打印dp数组，一般代码出了问题的情况dp数组肯定是有问题的；

代码实现遇到问题的时候，思考这三个问题：

这道题目我举例推导状态转移公式了么？
我打印dp数组的日志了么？
打印出来了dp数组和我想的一样么？

如果这灵魂三问自己都做到了，基本上这道题目也就解决了，或者更清晰的知道自己究竟是哪一点不明白，是状态转移不明白，还是实现代码不知道该怎么写，还是不理解遍历dp数组的顺序。

斐波那契数

斐波那契数，通常用 F(n) 表示，形成的序列称为斐波那契数列。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是： F(0) = 0，F(1) = 1 F(n) = F(n - 1) + F(n - 2)，其中 n > 1 给你n ，请计算 F(n) 。

示例 1：

输入：2
输出：1
解释：F(2) = F(1) + F(0) = 1 + 0 = 1

示例 2：

输入：3
输出：2
解释：F(3) = F(2) + F(1) = 1 + 1 = 2

示例 3：

输入：4
输出：3
解释：F(4) = F(3) + F(2) = 2 + 1 = 3

提示：

0 <= n <= 30

尝试方法论分析：

确定dp数组（dp table）以及下标的含义；
确定递推公式；
dp数组如何初始化；
确定遍历顺序；
举例推导dp数组；

1.斐波那契数列对应的dp数组显然是一维的，其下标i就是每个斐波那契数对应的下标；

2.递推公式很简单：F(i) = F(i - 1) + F(i - 2);

3.dp数组初始化也很简单：dp[0] = 0; dp[1] = 1; i =2;

4.遍历顺序从前往后；

5.举例如下，假设n = 10，dp数组打印出来就是0 1 1 2 3 5 8 13 21 34 55

整体代码如下：

#include<stdio.h>
#include<vector>
#include<iostream>
using namespace std;
class solution {
public:int fib(int n) {if (n <= 1)	return n;vector<int> dp(n + 1);dp[0] = 0;dp[1] = 1;for (int i = 2; i <= n; i++) {dp[i] = dp[i - 1] + dp[i - 2];}for (int i = 0; i <= n; i++) {cout << dp[i] << ' ';}cout << endl;return dp[n];}int fib1(int n){if (n <= 1)	return n;int dp[2];//降低空间复杂度到O(1)dp[0] = 0;dp[1] = 1;int sum = 0;for (int i = 2; i <= n; i++) {sum = dp[0] + dp[1];dp[0] = dp[1];dp[1] = sum;}return sum;}
};
int main() {cout << "Please enter the target length of fibnoacci sequence:" << endl;int n;cin >> n;solution myclass;cout << "The dp table will be shown as below:" << endl;int res = myclass.fib(n);cout << "The last number of this sequence is:" << res << endl;return 0;
}

爬楼梯

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

注意：给定 n 是一个正整数。

示例 1：

输入： 2
输出： 2
解释：有两种方法可以爬到楼顶。
- 1 阶 + 1 阶
- 2 阶

示例 2：

输入： 3
输出： 3
解释：有三种方法可以爬到楼顶。
- 1 阶 + 1 阶 + 1 阶
- 1 阶 + 2 阶
- 2 阶 + 1 阶

本题的关键点在于理解过程，走到n阶必然是从n - 1阶或者n - 2阶走上来的，所以只需要知道f(n - 1)和f(n - 2)就可以知道答案了；

只要想到这一点，就迎刃而解了；

至于从n-2到n阶就一定是走的两步而不是两个一步吗？

是的，因为如果走一步的话就是从n-1到n的情况了，已经涵盖进去，所以表达式只能是f(n) = f(n - 1) + f(n - 2);

五步：

1.确定dp数组及其下标含义：
dp[i]表示走到第i阶的方法种数；

2.确定递推公式：

dp[i] = dp[i - 1] + dp[i - 2]；看起来可能很难理解是如何推导出来的，举例就知道了：

3.初始化dp数组：

按照题意，不应该对dp[0]进行任何操作；dp[1] = 1; dp[2] = 2; i = 3;

4.遍历顺序：

正序；

5.举例dp数组： 1 2 3 5 8……，注意此处dp数组输出的起始下标为1

class Solution {
public:int climbStairs(int n) {if (n <= 1) return n; // 因为下面直接对dp[2]操作了，防止空指针//vector<int> dp(n + 1);int dp[3];dp[1] = 1;dp[2] = 2;for (int i = 3; i <= n; i++) { // 注意i是从3开始的int sum = dp[1] + dp[2];dp[1] = dp[2];dp[2] = sum;}return dp[2];}
};

使用最小花费爬楼梯

给你一个整数数组 cost ，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用，即可选择向上爬一个或者两个台阶。

你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。

请你计算并返回达到楼梯顶部的最低花费。

1.明确dp数组含义及其下标：

此时需要dp[i]一维数组，下标i为对应到达台阶，dp[i]的值为cost消耗；

2.确定递推公式：
到达第i个台阶的花费是由dp[i - 1]或dp[i - 2]决定的，分别为：

dp[i - 1] + cost[i - 1]; dp[i - 2] + cost[i - 2];

3.dp数组初始化：

题目描述中明确说了 “你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。”

也就是说到达第 0 个台阶是不花费的，但从第0个台阶往上跳的话，需要花费 cost[0]；

所以初始化 dp[0] = 0，dp[1] = 0;

4.确定遍历顺序：

显然，从前往后；

5.打印dp数组：

以题目示例2为例：

	int minCost(vector<int>& cost){vector<int> dp(cost.size() + 1);dp[0] = 0;dp[1] = 0;for(int i = 2; i <= cost.size(); i++){dp[i] = min(dp[i - 2] + cost[i - 2], dp[i - 1] + cost[i - 1]);}return dp[cost.size()];}