6.寻找旋转数组的最小数字
题目描述：把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。 输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。如：input:[3,4,5,1,2]，return：1 注：给出的所有元素都大于0，若数组大小为0，请返回0。
思路：本题通过遍历数组显然可以找到最小值，但本题考查点是二分查找，时间复杂度O(logn)，由于原数组非递减，所以我们旋转数组的第一元素（作为参照target）,与中间元素mid对比。
- 若array[mid] >= array[0]，左区间单调不减，最小值在mid右
- 若array[mid] < array[0]，左区间不单调，最小值在mid左
ps:对于等于的情况，如2，2，1，最小值在mid右边
代码：
public class Solution { // 1.遍历数组 public int minNumberInRotateArray(int [] array) { if (array == null || array.length == 0){ return 0; } int min = array[0]; for (int i = 1; i < array.length; ++i) { if (array[i] <= min) min = array[i]; else continue; } return min; } // 2.二分法 public int minNumberInRotateArray_1(int [] array) { if (array == null || array.length == 0){ return 0; } int l = 0, r = array.length - 1; while (l < r) { int mid = l + ((r - l) >> 1); if (array[mid] >= array[0]) { l = mid + 1; } else { r = mid; } } return array[l]; } }
7.斐波那契数列
题目描述：大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0，第1项是1）。
思路：状态转移方程：f(n) = f(n - 1) + f(n - 2)已给出，直接动态规划+空间压缩，比较常规。
代码：
public int Fibonacci(int n) { if (n < 2) return n; int pre1 = 0, pre2 = 1; for (int i = 2; i <= n; ++i) { int tmp = pre1 + pre2; pre1 = pre2; pre2 = tmp; } return pre2; }
8.跳台阶（爬楼梯）
题目描述：一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
注：先后次序不同算不同的结果。
思路：
法1：动态规划：类比上题，状态转移方程相同，直接动态规划（自底向上），状态并进行空间优化。
法2：动态规划：完全背包组合问题解法，可供选择为1和2，目标target（类似于背包最大体积）。
代码：
public class Solution { // 1. 动态规划（自底向上） public int jumpFloor(int target) { if (target == 0 || target == 1) return target; // ps：pre1 = 1(等同dp[0] = 1)，为了动态规划合理性设置 int pre1 = 1, pre2 = 1, tmp; for (int i = 2; i <= target; ++i) { tmp = pre1 + pre2; pre1 = pre2; pre2 = tmp; } return pre2; } // 2. 动态规划（完全背包） public int jumpFloor_1(int target) { int[] dp = new int[target + 1]; // 设置1，被其他值参考 dp[0] = 1; for (int i = 1; i <= target; ++i) { for (int j = 1; j <= 2; ++j) { if (j <= i){ dp[i] += dp[i - j]; } } } return dp[target]; } }
9.变态跳台阶
题目描述：一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
思路：
法1：动态规划（自底向上）：根据规律推导状态转移方程。
状态转移方程推导： f(n) = f(n - 1) + f(n - 2) + ... + f(0) ...1 f(n - 1) = f(n - 2) + ... + f(0) ...2 1 - 2 得：f(n) = 2f(n - 1)
法2：动态规划：类比跳台阶完全背包组合问题解法，只不过这里有1... n可供选择。
代码：
public class Solution { // 1. 数学推导 + 空间压缩 public int jumpFloorII(int target) { if (target == 0 || target == 1) return target; int pre = 1, cur = 0; for (int i = 2; i <= target; ++i) { cur = 2 * pre; pre = cur; } return cur; } // 2. 完全背包（动态规划） public int jumpFloorII(int target) { int[] dp = new int[target + 1]; dp[0] = 1; for (int i = 1; i <= target; ++i) { for (int j = 1; j <= target; ++j) { if (j <= i) { dp[i] += dp[i - j]; } } } return dp[target]; } }
10.矩形覆盖
题目描述：我们可以用2x1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2x1的小矩形无重叠地覆盖一个2xn的大矩形，总共有多少种方法？比如n=3时，2x3的矩形块有3种覆盖方法：
image.png
思路：本题关键如何找出状态转移方程：
1.n = 1： 只有一种情况， | 2.n = 2： 两种情况，二|| or ||二 3.n > 3： 只考虑最后一块的覆盖的两种情况，如下图
image.png
总方法数：f(n) = f(n - 1) + f(n - 2)，与上几个题相同，直接写代码。
代码：
public class Solution { public int rectCover(int target) { // 动态规划 if (target < 2) return target; int pre1 = 1, pre2 = 2, tmp; for (int i = 2; i < target; ++i) { tmp = pre1 + pre2; pre1 = pre2; pre2 = tmp; } return pre2; } }
