70. 爬楼梯

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

每次你可以爬 12 个台阶。你有多少种不同的方法可以爬到楼顶呢?

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

  1. 示例 1:

    1
    2
    3
    4
    5
    输入: 2
    输出: 2
    解释: 有两种方法可以爬到楼顶。
    1. 1 阶 + 1
    2. 2
  2. 示例 2:

    1
    2
    3
    4
    5
    6
    输入: 3
    输出: 3
    解释: 有三种方法可以爬到楼顶。
    1. 1 阶 + 1 阶 + 1
    2. 1 阶 + 2
    3. 2 阶 + 1

题解

1
2
3
4
5
6
7
8
9
int climbStairs(int n) {
int p = 0, q = 0, r = 1;
for (int i = 1; i <= n; ++i) {
p = q;
q = r;
r = p + q;
}
return r;
}

198. 打家劫舍

你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组,计算你不触动警报装置的情况下 ,一夜之内能够偷窃到的最高金额。

  1. 示例 1:

    1
    2
    3
    4
    输入:[1,2,3,1]
    输出:4
    解释:偷窃 1 号房屋 (金额 = 1) ,然后偷窃 3 号房屋 (金额 = 3)。
    偷窃到的最高金额 = 1 + 3 = 4
  2. 示例 2:

    1
    2
    3
    4
    输入:[2,7,9,3,1]
    输出:12
    解释:偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9),接着偷窃 5 号房屋 (金额 = 1)。
    偷窃到的最高金额 = 2 + 9 + 1 = 12
  • 提示:

    1
    2
    1 <= nums.length <= 100
    0 <= nums[i] <= 400

题 解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public int rob(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
int length = nums.length;
if (length == 1) {
return nums[0];
}
int[] dp = new int[length];
dp[0] = nums[0];
dp[1] = Math.max(nums[0], nums[1]);
for (int i = 2; i < length; i++) {
dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]);
}
return dp[length - 1];
}
}

120. 三角形最小路径和

给定一个三角形 triangle ,找出自顶向下的最小路径和。

每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。也就是说,如果正位于当前行的下标 i ,那么下一步可以移动到下一行的下标 ii + 1

  1. 示例 1:

    1
    2
    3
    4
    5
    6
    7
    8
    输入:triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
    输出:11
    解释:如下面简图所示:
    2
    3 4
    6 5 7
    4 1 8 3
    自顶向下的最小路径和为 11(即,2 + 3 + 5 + 1 = 11)。
  2. 示例 2:

    1
    2
    输入:triangle = [[-10]]
    输出:-10
  • 提示:

    1. 1 <= triangle.length <= 200
    2. triangle[0].length == 1
    3. triangle[i].length == triangle[i - 1].length + 1
    4. -104 <= triangle[i][j] <= 104

题 解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public int minimumTotal(List<List<Integer>> triangle) {
int n = triangle.size();
// dp[i][j] 表示从点 (i, j) 到底边的最小路径和。
int[][] dp = new int[n + 1][n + 1];
// 从三角形的最后一行开始递推。
for (int i = n - 1; i >= 0; i--) {
for (int j = 0; j <= i; j++) {
dp[i][j] = Math.min(dp[i + 1][j], dp[i + 1][j + 1]) + triangle.get(i).get(j);
}
}
return dp[0][0];
}
}