思考
刚开始看到这个题目的时候可能没什么思路，不过我们可以一点点的想下去，我们假设青蛙跳上一个 n 级的台阶总共有多少种跳法 f(n)种跳法，那当 n = 0 时，f(0) = 0，没有台阶当然没有跳法。n = 1，f(1) = 1;只有一个台阶的时候，只能跳 1 个;n = 2，f(2) = 2，当有两个台阶的时候，可以有 2 种跳法，一个一个跳和一下跳 2 个，那如果我们有三个台阶的话，是不是将一个台阶和两个台阶的总和加起来就可以了呢?所以我们就可以想到 f(3) = f(2) + f(1)，所以我们能推导出 f(n) = f(n – 1) + f(n – 2);
编码
上面的分析可以想到，那么接下来我们就需要用代码来实现了，对于需要使用到之前的记录，我们可以考虑用一维数组来记录，所以就有了下面的这段代码。
- public int dp(int n) {
- if (n <= 0) {
- return 0;
- }
- int[] dp = new int[n + 1];
- dp[0] = 0;
- dp[1] = 1;
- dp[2] = 2;
- // 之所以要从 3 开始，是因为 2 不符合下面的规则
- for (int i = 3; i <= n; i++) {
- dp[i] = dp[i – 1] + dp[i – 2];
- }
- return dp[n];
- }
解释下上面的代码，首先我们创建了一个一维数组 dp，用于记录每个台阶有的跳法，然后从索引三开始遍历，运用公式f(n) = f(n – 1) + f(n – 2); 进行赋值，结果直接输出 dp[n] 对应的数值即可。
分析
通过上面的案例，我们思考一下对于动态规划的题目我们需要怎么做，我们一开始定义了 n 级台阶有 f(n) 种跳法，然后通过模拟的方式计算出f(0),f(1),f(2)，接着我们找到了 f(n) = f(n – 1) + f(n – 2); 的关系。按照这种思路我们可以总结出三个步骤，分别是
- 定义变量：把已知的和需要求解的，定义出变量，如上面的 n 和 f(n);
- 寻找表达式：找到 f(n) 和 f(n – 1) 以及 f(n – 2)，等情况的表达式，如上面的 f(n) = f(n – 1) + f(n – 2)，这一步往往是最难的;
- 寻找初始值：确保找到所有的临界条件，如上面的 f(0) = 0, f(1) = 1, f(2) = 2;
上面的步骤是通用步骤，往往在第一步的时候我们设置的 f(n) 是一个数组，根据具体的场景可能是一维数组也有可能是二维数组，上面的例子我们定义的就是一维数组，而且往往我们需要求解什么就定义什么数组。
下面我们通过这种方式再看一道 LeetCode 的原题
