本文主要是介绍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()];}
这篇关于Day 38 理论基础 509. 斐波那契数 70. 爬楼梯 746. 使用最小花费爬楼梯的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
