算法笔记：Day-09（初始动态规划）

509. 斐波那契数

斐波那契数 （通常用 F(n) 表示）形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：

F(0) = 0，F(1) = 1
F(n) = F(n - 1) + F(n - 2)，其中 n > 1

给定 n ，请计算 F(n) 。

示例 1：

输入：n = 2
输出：1
解释：F(2) = F(1) + F(0) = 1 + 0 = 1

示例 2：

输入：n = 3
输出：2
解释：F(3) = F(2) + F(1) = 1 + 1 = 2

示例 3：

输入：n = 4
输出：3
解释：F(4) = F(3) + F(2) = 2 + 1 = 3

提示：

• 0 <= n <= 30

class Solution {public int fib(int n) {if(n<=1){return n;}int a=0,b=1,ans=0;for(int i=2;i<=n;i++){ans=a+b;a=b;b=ans;}return ans;}
}

70. 爬楼梯

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

  每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

  示例 1：

  输入：n = 2
  输出：2
  解释：有两种方法可以爬到楼顶。
  1. 1 阶 + 1 阶
  2. 2 阶
  

  示例 2：

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

  提示：

  • 1 <= n <= 45

class Solution {public int climbStairs(int n) {int a=1,b=2;if(n==1)return a;if(n==2)return b;int ans=0;for(int i=3;i<=n;i++){ans=a+b;a=b;b=ans;}return ans;}
}

就是在一些最优子结构的基础上跳跃。
n==3时 有三种爬法 因为一次可以爬一阶或者两阶，所以在dp[1]的基础上跳两阶加上dp[2]跳一阶，就是两个最优子结构相加。

1. 1 阶 + 2 阶
2. 1 阶 + 1 阶 + 1 阶
3. 2 阶 + 1 阶

55. 跳跃游戏

给你一个非负整数数组 nums ，你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个下标，如果可以，返回 true ；否则，返回 false 。

示例 1：

输入：nums = [2,3,1,1,4]
输出：true
解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。

示例 2：

输入：nums = [3,2,1,0,4]
输出：false
解释：无论怎样，总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 ， 所以永远不可能到达最后一个下标。

提示：

• 1 <= nums.length <= 104
• 0 <= nums[i] <= 105

class Solution {public boolean canJump(int[] nums) {int maxStep=0,len=nums.length;for(int i=0;i<len;i++){if(i>maxStep){return false;}maxStep=Math.max(maxStep,i+nums[i]);if(maxStep>=len-1){return true;}}return false;}
}

遍历数组更新最远距离，如果i超过了最远距离，说明跳不到 i 索引，即跳不到终点。

45. 跳跃游戏 II

给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。

每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说，如果你在 nums[i] 处，你可以跳转到任意 nums[i + j] 处:

• 0 <= j <= nums[i]
• i + j < n

返回到达 nums[n - 1] 的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]。

示例 1:

输入: nums = [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。

示例 2:

输入: nums = [2,3,0,1,4]
输出: 2

class Solution {public int jump(int[] nums) {int len=nums.length;int maxStep=0;int end=0;int ans=0;for(int i=0;i<len-1;i++){maxStep=Math.max(maxStep,i+nums[i]);if(i==end){ans++;end=maxStep;}}return ans;}
}

338. 比特位计数

给你一个整数 n ，对于 0 <= i <= n 中的每个 i ，计算其二进制表示中 1 的个数 ，返回一个长度为 n + 1 的数组 ans 作为答案。

示例 1：

输入：n = 2
输出：[0,1,1]
解释：
0 --> 0
1 --> 1
2 --> 10

示例 2：

输入：n = 5
输出：[0,1,1,2,1,2]
解释：
0 --> 0
1 --> 1
2 --> 10
3 --> 11
4 --> 100
5 --> 101

class Solution {public int[] countBits(int n) {int[] ans=new int[n+1];int temp=0;for(int i=0;i<=n;i++){ans[i]=countOnes(i);}return ans;}public int countOnes(int x){int count=0;while(x!=0){x &= (x-1);count++;}return count;}
}

三种计算二进制中1的个数

1. 利用位运算

public static int countOnes(int n) {int count = 0;while (n != 0) {count += n & 1; // 检查最低位是否为 1n >>>= 1;       // 无符号右移 1 位}return count;}

2. 利用内置方法

public class CountOnes {public static void main(String[] args) {int number = 29; // 例如：29 的二进制是 11101int count = Integer.bitCount(number);System.out.println("1 的个数: " + count);}
}

3. 利用Brian Kernighan 算法

public static int countOnes(int n) {int count = 0;while (n != 0) {n &= (n - 1); // 将最低位的 1 清零count++;}return count;}

大佬的解法也不错

198. 打家劫舍

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

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

示例 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 。

解法一：
class Solution {public int rob(int[] nums) {int len=nums.length;int[] dp=new int[len];if(len==0)return 0;if(len==1)return nums[0];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];}
}
解法二：
class Solution {public int rob(int[] nums) {if (nums == null || nums.length == 0) {return 0;}int length = nums.length;int first=0,second=0;for (int i = 0; i < length; i++) {int temp = second;second = Math.max(first + nums[i], second);first = temp;}return second;}
}

解法二：因为每个最优子结构只与连两个房子有关。不需要考虑溢出问题，而且可以从0开始遍历，且空间复杂度为O(1)。
这个解法对于打家劫舍2有很大的优势。

213. 打家劫舍 II

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

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

示例 1：

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

示例 2：

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

示例 3：

输入：nums = [1,2,3]
输出：3

class Solution {public int rob(int[] nums) {if(nums.length == 0) return 0;if(nums.length == 1) return nums[0];return Math.max(myRob(Arrays.copyOfRange(nums, 0, nums.length - 1)), myRob(Arrays.copyOfRange(nums, 1, nums.length)));}private int myRob(int[] nums) {int pre = 0, cur = 0, tmp;for(int num : nums) {tmp = cur;cur = Math.max(pre + num, cur);pre = tmp;}return cur;}
}

这个解法简单优雅，不用考虑溢出问题。

class Solution {public int rob(int[] nums) {int len=nums.length;if(len==0)return 0;if(len==1)return nums[0];return Math.max(myRob(Arrays.copyOfRange(nums,0,len-1)),myRob(Arrays.copyOfRange(nums,1,len)));}public int myRob(int[] nums){int len=nums.length;int[] dp=new int[len];if(len==0)return 0;if(len==1)return nums[0];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];}
}

两个方法考虑溢出，因为如果len==2的话myRob会出现溢出问题，烦死人了，如果时OI赛制我已经死了。