70. Climbing Stairs (Easy)

题目描述
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？注意：给定 n 是一个正整数。
示例
输入： 2
输出： 2
解释： 有两种方法可以爬到楼顶。
1. 1 阶 + 1 阶
2. 2 阶
思路
dp[i] = dp[i-1]+dp[i-2]

  1. class Solution {
  2.     public int climbStairs(int n) {
  3.         int[] stair = new int[n+1];
  4.         stair[0] = 1;
  5.         stair[1] = 1;
  6.         for(int i=2; i<n+1; i++){
  7.             stair[i] = stair[i-1]+stair[i-2];
  8.         }
  9.         return stair[n];
  10.     }
  11. }

结果
image.png

内存优化

思路 ：由于每次计算只需要前两次的数值，舍弃原本的int[n]数组，用n1，n2代替。

  1. class Solution {
  2.     public int climbStairs(int n) {
  3.         int n1 = 1;
  4.         int n2 = 1;
  5.         for(int i=2; i<n+1; i++){
  6.             int tmp = n1+n2;
  7.             n1 = n2;
  8.             n2 = tmp;
  9.         }
  10.         return n2;
  11.     }
  12. }

结果
image.png

198. House Robber (Easy)

题目描述
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
示例
输入：[1,2,3,1]
输出：4
解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
偷窃到的最高金额 = 1 + 3 = 4 。
思路
dp[i] = Math.max(dp[i-1],dp[i-2]+nums[i])

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

内存优化

  1. class Solution {
  2.     public int rob(int[] nums) {
  3.         if(nums==null){
  4.             return 0;
  5.         }
  6.         int len = nums.length;
  7.         if(len==0){
  8.             return 0;
  9.         }else if(len==1){
  10.             return nums[0];
  11.         }
  12.         int n1 = 0;
  13.         int n2 = nums[0];
  14.         for(int i=1; i<len; i++){
  15.             int tmp = Math.max(n2,n1+nums[i]);
  16.             n1 = n2;
  17.             n2 = tmp;
  18.         }
  19.         return n2;
  20.     }
  21. }

213. House Robber II (Medium)

题目描述
你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。
给定一个代表每个房屋存放金额的非负整数数组，计算你 在不触动警报装置的情况下 ，能够偷窃到的最高金额。
示例
输入：nums = [2,3,2]
输出：3
解释：你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。
思路
同上，但需分开考虑数组[0,n-1]和[1,n]

  1. class Solution {
  2.     public int rob(int[] nums) {
  3.         if(nums.length == 0) return 0;
  4.         if(nums.length == 1) return nums[0];
  5.         return Math.max(myRob(Arrays.copyOfRange(nums, 0, nums.length - 1)), 
  6.                         myRob(Arrays.copyOfRange(nums, 1, nums.length)));
  7.     }
  8.     private int myRob(int[] nums) {
  9.         int pre = 0, cur = 0, tmp;
  10.         for(int num : nums) {
  11.             tmp = cur;
  12.             cur = Math.max(pre + num, cur);
  13.             pre = tmp;
  14.         }
  15.         return cur;
  16.     }
  17. }