首先我觉得得弄明白『动态规划』算法到底是个什么？
上述这张图是摘自截取百度百科对动态规划的定义，我个人觉得主要是有如下几个特点
- 和分治法类似，将待求解问题划分成若干类似原理子问题，然后从子问题入手最后得到原问题的解
- 往往是题干出现“最大”“最小”“最好”“最多”等最优化性质的词的时候可以优先考虑动态规划思想（当然也不一定是这样，只是我个人刷题的经验而已）
- 动态规划很多题往往是需要按照如下两个步骤
- 确定状态表示的含义，同时确定好基本的初始值
- 状态转移方程或者不同状态之间存在的依赖关系
以上大致确定了基本的『动态规划』思想，那么接下来就步入正题：
最近刚好看到LeetCode上有一个『21天掌握动态规划的刷题指南』
1. 第一天 基础动态规划
1.1 509. 斐波那契数
斐波那契数，通常用 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
提示：
C++代码如下：
class Solution { public: int fib(int n) { int dp[n + 1]; if (n <= 1) { return n; } dp[0] = 0, dp[1] = 1; for (int i = 2; i <= n; i++) { dp[i] = dp[i - 1] + dp[i - 2]; } return dp[n]; } };
Java代码如下：
class Solution { public int fib(int n) { int[] dp = new int[n + 1]; if (n <= 1) { return n; } dp[0] = 0; dp[1] = 1; for (int i = 2; i <= n; i++) { dp[i] = dp[i - 1] + dp[i - 2]; } return dp[n]; } }
优化1：
C++代码如下：
class Solution { public: int fib(int n) { if (n <= 1) { return n; } int a = 0; int b = 1; int sum = 0; for (int i = 2; i <= n; i++) { sum = a + b; a = b; b = sum; } return b; } };
Java代码如下：
class Solution { public int fib(int n) { if (n <= 1) { return n; } int a = 0; int b = 1; int sum = 0; for (int i = 2; i <= n; i++) { sum = a + b; a = b; b = sum; } return b; }
优化2
对于这个题的公式而言，很容易联想到高中所学的求通项公式的知识。
查阅资料，找到了一个比较符合当时中学阶段求通项公式的资料
可以看到斐波那契数列通项公式为：
C++代码：
class Solution { public: int fib(int n) { double a = (1 + sqrt(5)) / 2; double qa = pow(a,n); double b = (1 - sqrt(5)) / 2; double qb = pow(b,n); double res = ( 1 / sqrt(5) * (qa - qb)); return (int) res; } };
Java代码：
class Solution { public int fib(int n) { double a = (1 + Math.sqrt(5)) / 2; double qa = Math.pow(a,n); double b = (1 - Math.sqrt(5)) / 2; double qb = Math.pow(b,n); double res = ( (1 / Math.sqrt(5)) * (qa - qb) % 1000000007); return (int)res; } }
1.2 70. 爬楼梯
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
注意：给定 n 是一个正整数。
示例 1：
输入： 2 输出： 2 解释： 有两种方法可以爬到楼顶。 1. 1 阶 + 1 阶 2. 2 阶
示例 2：
输入： 3 输出： 3 解释： 有三种方法可以爬到楼顶。 1. 1 阶 + 1 阶 + 1 阶 2. 1 阶 + 2 阶 3. 2 阶 + 1 阶
Java代码如下：
class Solution { public int climbStairs(int n) { if (n <= 2) { return n; } int[] dp = new int[n + 1]; dp[1] = 1; dp[2] = 2; for (int i = 3; i <= n; i++) { dp[i] = dp[i - 1] + dp[i - 2]; } return dp[n]; } }
可以发现和509题斐波那契数很像，只是初始值不一样，那么用滚动数组优化空间复杂度之后如下：
C++代码如下：
class Solution { public: int climbStairs(int n) { long a = 1, b = 2; long sum = 0; if (n <= 2) { return n; } for (int i = 3; i <= n; i++) { sum = a + b; a = b; b = sum; } return (int)b; } };
Java代码如下：
class Solution { public int climbStairs(int n) { if (n <= 2) { return n; } long a = 1, b = 2; long sum = 0; for (int i = 3; i <= n; i++) { sum = a + b; a = b; b = sum; } return (int) b; } }
同样的，这题也可以给出通项公式的做法，具体的代码可以参考官方题解的。
1.3 746. 使用最小花费爬楼梯
数组的每个下标作为一个阶梯，第 i 个阶梯对应着一个非负数的体力花费值 cost[i]（下标从 0 开始）。
每当你爬上一个阶梯你都要花费对应的体力值，一旦支付了相应的体力值，你就可以选择向上爬一个阶梯或者爬两个阶梯。
请你找出达到楼层顶部的最低花费。在开始时，你可以选择从下标为 0 或 1 的元素作为初始阶梯。
示例 1：
输入：cost = [10, 15, 20] 输出：15 解释：最低花费是从 cost[1] 开始，然后走两步即可到阶梯顶，一共花费 15 。
示例 2：
输入：cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1] 输出：6 解释：最低花费方式是从 cost[0] 开始，逐个经过那些 1 ，跳过 cost[3] ，一共花费 6 。
这个题和上述两题『509.斐波那契数列』、『70.爬楼梯』很相似，不同点在于爬上一个阶梯需要花费对应的体力值，也就是需要多一个对比给定的c o s t costcost数组的值的步骤。
Java代码如下：
class Solution { public int minCostClimbingStairs(int[] cost) { int n = cost.length; int[] dp = new int[n + 1]; dp[0] = 0; dp[1] = 0; for (int i = 2; i <=n ; i++) { dp[i] = Math.min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]); } return dp[n]; } }
滚动数组优化后的代码展示：
class Solution { public int minCostClimbingStairs(int[] cost) { int n = cost.length; int a = 0, b = 0; int sum = 0; for (int i = 2; i <=n ; i++) { sum = Math.min(a + cost[i - 1], b + cost[i - 2]); b = a; a = sum; } return a; } }
