斐波那锲数问题

leetcode 70 爬楼梯

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

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

经典的斐波那锲数问题。可以从第(n-1)级台阶或者(n-2)级台阶跳到第n级台阶。
因此状态转移方程为f(n) = f(n-1)+f(n-2)

public int climbStairs(int n) {
        if (n < 1) {
            return 0;
        }
        if (n == 1 || n == 2) {
            return n;
        }
        int a = 1;
        int b = 2;
        int res = 0;
        for (int i = 2; i < n; i++) {
            res = a + b;
            a = b;
            b = res;
        }
        return res;
    }

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。示例 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 。

假设只有一户人家。显然结果就是直接偷这一户人家。比如nums =[2],则结果为2。记为dp[0]

假设有两户人家。显然就是偷两户人家，则偷现金多的一个。nums=[2,7]，则结果为7。记为dp[1]

假设有三户人家。nums=[2,7,9]，则结果为要么偷这家。最多为dp[0]+9=11,要么不偷这家，最多为dp[1]=7。因此dp[2]=11

假设有四户人家。nums=[2,7,9,3]，则结果为要么偷这家。最多为dp[1]+3=10,要么不偷这家，最多为dp[2]=11。因此dp[3]=11

从中可以看出。状态转移方程为dp[i] = Math.max(dp[i-1],dp[i-2]+nums[i]); 初始条件为dp[0] = nums[0]; dp[1] = Math.max(nums[0],nums[1]);

下面的代码解析给出了递归---》动态规划---》空间压缩的过程

//递归解法
    public int robdigui(int[] nums,int index) {
        if(index == 0){
            return nums[0];
        }
        if(index == 1){
            return Math.max(nums[0],nums[1]);
        }
        return Math.max(robdigui(nums,index-1),robdigui(nums,index-2)+nums[index]);
    }

    //动态规划解法
    public int rob(int[] nums) {
        if(nums == null || nums.length == 0){
            return 0;
        }
        int len = nums.length;
        if(len == 1){
            return nums[0];
        }
        int[] dp = new int[len];
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0],nums[1]);
        for(int i = 2;i< len;i++){
            dp[i] = Math.max(dp[i-1],dp[i-2]+nums[i]);
        }
        return dp[len-1];
    }


    //动态规划解法的空间压缩
    public int robdp(int[] nums) {

        if(nums == null || nums.length == 0){
            return 0;
        }
        int len = nums.length;
        if(len == 1){
            return nums[0];
        }
        int a = nums[0];
        int b = Math.max(nums[0],nums[1]);
        int c = 0;
        for(int i = 2;i< len;i++){
            c = Math.max(b,a+nums[i]);
            a = b;
            b = c;

        }
        return c;
    }

213. 打家劫舍 II

你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都围成一圈，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

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

示例 1: 输入: [2,3,2] 输出: 3
解释: 你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。

示例 2: 输入: [1,2,3,1] 输出: 4
解释: 你可以先偷窃 1 号房屋（金额 = 1），然后偷窃 3 号房屋（金额 = 3）。
偷窃到的最高金额 = 1 + 3 = 4 。

和上一题的一个区别就是首尾不能相连，因此相当于偷0--》n-2和1--》n-1的较大值

代码如下

public int rob(int[] nums) {
        if(nums == null || nums.length == 0){
            return 0;
        }
        int len = nums.length;
        if(len ==  1){
            return nums[0];
        }
        if(len ==  2){
            return nums[0]>nums[1]?nums[0]:nums[1];
        }
        return Math.max(help(nums,0,len-2),help(nums,1,len-1));
        
    }
    private int help(int[] nums,int start,int end){
        int[] dp = new int[end-start+1];
        dp[0] = nums[start];
        dp[1] = Math.max(nums[start+1],nums[start]);
        
        for(int i = start+2;i<=end;i++ ){
            dp[i-start] = Math.max(dp[i-start-1],dp[i-start-2]+nums[i]);
        }
        return dp[end-start];
        
    }