小试牛刀
爬楼梯问题
问题
假设你正在爬楼梯。需要
n阶你才能到达楼顶。每次你可以爬1或2个台阶。你有多少种不同的方法可以爬到楼顶呢？
分析
初始分析
-
对第1阶楼梯
只有一种可能，爬1层
-
对于第2阶楼梯
有2种可能：
- 从第一阶爬1阶到达
- 从地面（第0阶）爬2个台阶到达
到达任意台阶的方式
假设第n个台阶
有两种爬法：
- 从n-1阶爬1阶到达n阶
- 从n-2阶爬2阶到达n阶
推出一般公式 : 到达当前台阶 选择 {n-1爬1阶，n-2爬2阶}
通俗讲： 当前的台阶(n)可能数由之前的n-1台阶和n-2台阶数据决定
f(n) = f(n-1) + f(n-2);
解决方案
斐波拉切数列法
java"> public int fib(int n) {if (n == 0 || n == 1) return 1;int res = fib(n - 1) + fib(n-2);return res;}
动态规划
-
定义数组记录每一阶的可能数
java">int[] dp = new int[n + 1]; -
初始化到达dp[0],dp[1]
dp[0] = 1; dp[1] = 1; -
最右解，即一般状态转义方程
java">for(int i=2; i<=n;i++){dp[i] = dp[i-1] + dp[i-2]; }
优化：状态压缩
当前n的台阶可能性只与前两个f(n-1),f(n-2)的状态有关，我们可以不需要记录到数组，只需要用两个变量记录即可。
java">class Solution {public int climbStairs(int n) {if(n==1) return 1;if(n==2) return 2;int a = 1;int b = 1;int c = 0;for(int i =2;i<=n;i++){c = a+b;a = b;b = c;}return c;}
}
相似问题
-
[力扣70] 70. 爬楼梯 - 力扣（LeetCode）
-
[力扣127] LCR 127. 跳跃训练 - 力扣（LeetCode）
-
[力扣746] 746. 使用最小花费爬楼梯 - 力扣（LeetCode）
数字金字塔问题
问题
如图所示，找出登上金字塔的最短路线（路径上的数字总和最小）。
注意： 每一个向上的路径，只有左上和右上(例如14的向上线路: 14->34, 45的向上线路: 45->34, 45->18)
分析
如何到达塔顶
到达金字塔顶(45) 有两种可能： 经过(20)， 经过(33)
如何到达塔顶的下一层
到达（20)需要经过(34),(18)
到达(33)需要经过(18), (30)
到达塔的第二层(34,18,30)
从图中发现： 09–>18的路径最短到达第二层，18->20的路径最短到达第三层, 20–>45的路径最短到达塔顶。
解决方案
修改图形
将图形调整为一个直角三角形。
定义记忆化数组
可以定义一个二维数组int [][] dp 记录中间的计算结果（即行走路径的结果)
java">List<List<Integer>> nums = new ArrayList<>();
int n = nums.length();
int[][] dp = new int[n];
存储第一行数据到记忆化数组中
记录row=0行的所有数据到记忆化数组。
java">for(int col=0; col<n;col++){dp[0][col] = nums.get(0).get(col);
}
定义状态转义方程
从第二行row=1开始，其路径由下一层的当前列和其下一列计算完成。
例如： dp[1,0]结果 与 dp[0][0] 和dp[0][1]计算而来。
java">for (int row = 1; row < n; row++) {for (int col = 0; col < n-row; col++) {dp[row][col] = Math.min(dp[row-1][col+1],dp[row-1][col])+ nums.get(row).get(col);}
}
获取结果
观察结果得走到顶层的为dp[3][0]
参考实现
java">public class Pyramid {public static void main(String[] args) {List<List<Integer>> nums = new ArrayList<>();nums.add(new ArrayList<Integer>() {{add(14);add(45);add(9);add(11);}});nums.add(new ArrayList<Integer>() {{add(34);add(18);add(30);}});nums.add(new ArrayList<Integer>() {{add(20);add(33);}});nums.add(new ArrayList<Integer>() {{add(45);}});int n = nums.size();int[][] dp = new int[n][n];for (int col = 0; col < n; col++) {dp[0][col] = nums.get(0).get(col);}for (int row = 1; row < n; row++) {for (int col = 0; col < n-row; col++) {dp[row][col] = Math.min(dp[row-1][col+1],dp[row-1][col]) + nums.get(row).get(col);}}System.out.println(Arrays.deepToString(dp));}
}
运行结果
[[14, 45, 9, 11], [48, 27, 39, 0], [47, 60, 0, 0], [92, 0, 0, 0]]
力扣经典额外难题
最小路径和
问题
[力扣64] 64. 最小路径和 - 力扣（LeetCode）
问题描述
给定一个包含非负整数的 *m* x *n* 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
**说明：**每次只能向下或者向右移动一步。
示例 1：
java">输入：grid = [[1,3,1],[1,5,1],[4,2,1]]
输出：7
解释：因为路径 1→3→1→1→1 的总和最小。
示例 2：
java">输入：grid = [[1,2,3],[4,5,6]]
输出：12
解决方案
行走路径只能朝右或者朝下。
两个例外：
- 例外1： 如果是最上面一行(row=0)，当前路径只能朝下。
java">for(int col =1; col< n;col++ ){dp[0][col] = grid[0][col]+dp[0][col-1];
}
- 例外2： 如果是最左侧列(col=0),当前路径只能朝下
java">for(int row =1; row< m;row++){dp[i][0] = grid[row][0]+dp[row-1][0];
}
参考实现
java">class Solution {public int minPathSum(int[][] grid) {int m = grid.length;int n = grid[0].length;int[][] dp = new int[m][n];dp[0][0]= grid[0][0];//当列位0时,只能朝下，当前dp[行][0] = dp[上一行][0]+ 当前数据for(int row =1; row< m;row++){dp[row][0] = grid[row][0]+dp[row-1][0];}//当行为0时,只能朝右移动，当前dp[0][列] = dp[0][上一列]for(int col = 1; col < n; col++ ){dp[0][col] = grid[0][col]+dp[0][col-1];}for(int row =1;row < m; row++){for(int col = 1; col < n; col++){int value = grid[row][col];dp[row][col] = Math.min(dp[row-1][col],dp[row][col-1])+value;}}return dp[m-1][n-1];}
}
三角形最小路径和
题目
[力扣120] 120. 三角形最小路径和 - 力扣（LeetCode）
题目描述
给定一个三角形 triangle ，找出自顶向下的最小路径和。
每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。也就是说，如果正位于当前行的下标 i ，那么下一步可以移动到下一行的下标 i 或 i + 1 。
示例 1：
java">输入：triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
输出：11
解释：如下面简图所示：23 46 5 7
4 1 8 3
自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。
示例 2：
java">输入：triangle = [[-10]]
输出：-10
解决方案
类似于金字塔问题。
