1. 打家劫舍
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
示例 1：
输入：[1,2,3,1]
输出：4
解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
偷窃到的最高金额 = 1 + 3 = 4 。
示例 2：
输入：[2,7,9,3,1]
输出：12
解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
偷窃到的最高金额 = 2 + 9 + 1 = 12 。
提示：
1 <= nums.length <= 100
0 <= nums[i] <= 400
出处：
https://edu.csdn.net/practice/23885004
代码：
public class rob { public static class Solution { public int rob(int[] nums) { if (nums.length == 0) return 0; if (nums.length == 1) return nums[0]; int result[] = new int[nums.length]; result[0] = nums[0]; result[1] = Math.max(nums[0], nums[1]); for (int i = 2; i < result.length; i++) { result[i] = Math.max(result[i - 1], result[i - 2] + nums[i]); } return result[result.length - 1]; } } public static void main(String[] args) { Solution s = new Solution(); int[] nums = {1,2,3,1}; System.out.println(s.rob(nums)); int[] nums1 = {2,7,9,3,1}; System.out.println(s.rob(nums1)); } }
输出：
4
12
2. 戳气球
有 n 个气球，编号为0 到 n - 1，每个气球上都标有一个数字，这些数字存在数组 nums 中。
现在要求你戳破所有的气球。戳破第 i 个气球，你可以获得 nums[i - 1] * nums[i] * nums[i + 1] 枚硬币。 这里的 i - 1 和 i + 1 代表和 i 相邻的两个气球的序号。如果 i - 1或 i + 1 超出了数组的边界，那么就当它是一个数字为 1 的气球。
求所能获得硬币的最大数量。
示例 1：
输入：nums = [3,1,5,8]
输出：167
解释：
nums = [3,1,5,8] --> [3,5,8] --> [3,8] --> [8] --> []
coins = 3*1*5 + 3*5*8 + 1*3*8 + 1*8*1 = 167
示例 2：
输入：nums = [1,5]
输出：10
提示：
n == nums.length
1 <= n <= 500
0 <= nums[i] <= 100
出处：
https://edu.csdn.net/practice/23885005
代码：
public class maxCoins { public static class Solution { public int maxCoins(int[] iNums) { int n = iNums.length; int[] nums = new int[n + 2]; for (int i = 0; i < n; i++) nums[i + 1] = iNums[i]; nums[0] = nums[n + 1] = 1; int[][] dp = new int[n + 2][n + 2]; for (int k = 1; k <= n; k++) { for (int i = 1; i <= n - k + 1; i++) { int j = i + k - 1; for (int x = i; x <= j; x++) { dp[i][j] = Math.max(dp[i][j], dp[i][x - 1] + nums[i - 1] * nums[x] * nums[j + 1] + dp[x + 1][j]); } } } return dp[1][n]; } } public static void main(String[] args) { Solution s = new Solution(); int[] nums = {3,1,5,8}; System.out.println(s.maxCoins(nums)); int[] nums1 = {1,5}; System.out.println(s.maxCoins(nums1)); } }
输出：
167
10
3. 最小路径和
给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
说明：每次只能向下或者向右移动一步。
示例 1：
输入：grid = [[1,3,1],[1,5,1],[4,2,1]]
输出：7
解释：因为路径 1→3→1→1→1 的总和最小。
示例 2：
输入：grid = [[1,2,3],[4,5,6]]
输出：12
提示：
m == grid.length
n == grid[i].length
1 <= m, n <= 200
0 <= grid[i][j] <= 100
出处：
https://edu.csdn.net/practice/23885006
代码：
public class minPathSum { public static class Solution { public int minPathSum(int[][] grid) { int m = grid.length; int n = grid[0].length; int sum = 0; if (m < 1 || n < 1) return 0; if (m == 1) { for (int i = 0; i < n; i++) { sum = sum + grid[0][i]; } return sum; } if (n == 1) { for (int i = 0; i < m; i++) { sum = sum + grid[i][0]; } return sum; } int[][] dp = new int[m][n]; dp[0][0] = grid[0][0]; for (int k = 1; k < m; k++) { dp[k][0] = grid[k][0] + dp[k - 1][0]; } for (int l = 1; l < n; l++) { dp[0][l] = grid[0][l] + dp[0][l - 1]; } for (int k = 1; k < m; k++) { for (int l = 1; l < n; l++) { dp[k][l] = grid[k][l] + Math.min(dp[k - 1][l], dp[k][l - 1]); } } return dp[m - 1][n - 1]; } } public static void main(String[] args) { Solution s = new Solution(); int[][] nums = {{1,3,1},{1,5,1},{4,2,1}}; System.out.println(s.minPathSum(nums)); int[][] nums1 = {{1,2,3},{4,5,6}}; System.out.println(s.minPathSum(nums1)); } }
输出：
7
12
