持续更新中（解题思路写在代码注释里）
1、爬楼梯
假设你正在爬楼梯。需要 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 阶
public static int climbStairs(int n) { /** * 爬楼梯的方案数为爬到n-1阶的方案数（只剩一步到楼顶）加上爬到n-2阶的方案数（只剩一次两步到楼顶） * 可知符合方案数 dp[n] = dp[n-1] + dp[n-2] * dp[0]=0, dp[1]=1,dp[2]=2 */ if(n == 1){ return 1; } int []dp = new int[n+1]; dp[0] = 0; dp[1] = 1; dp[2] = 2; for (int i = 3; i <= n; i++) { dp[i] = dp[i-1] + dp[i-2]; } return dp[n]; }
2、最大子序列
给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
示例 1：
输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
示例 2：
输入：nums = [1]
输出：1
示例 3：
输入：nums = [0]
输出：0
示例 4：
输入：nums = [-1]
输出：-1
示例 5：
输入：nums = [-100000]
输出：-100000
提示：
1 <= nums.length <= 3 * 104
-105 <= nums[i] <= 105
public static int maxSubArray(int[] nums) { /** * 方法一： 暴力枚举 */ // int n = nums.length; // int big = nums[0]; // int index1 = 0; // int index2 = 0; // int temp = nums[0]; // // for(int i=0;i<n;i++) { // temp = nums[i]; // if(temp>big) { // big=temp; // } // index1=i; // index2=i; // for(int j=i+1;j<n;j++) { // temp = temp+nums[j]; // if(temp > big) { // index2 = j; // big = temp; // } // } // } // // System.out.println(big); /** * 方法二： 动态规划 * * dp[i]表示以nums[i]结尾的最大序列和 * 当i=0时，dp[0] = nums[0] * 当i>0时，dp[i] = max{ (dp[i-1]+nums[i]) , nums[i] } * * 再找出dp[]中最大即可 */ int []dp = new int[nums.length]; dp[0] = nums[0]; for(int i=1;i<nums.length;i++) { dp[i] = Math.max((dp[i-1]+nums[i]), nums[i]); } int big = dp[0]; for(int i=1;i<dp.length;i++) { if(dp[i] > big) { big = dp[i]; } } return big; }
3、杨辉三角
给定一个非负整数 numRows，生成「杨辉三角」的前 numRows行。
在「杨辉三角」中，每个数是它左上方和右上方的数的和。
示例 1:
输入: numRows = 5
输出: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]
示例 2:
输入: numRows = 1
输出: [[1]]
提示:
1 <= numRows <= 30
class Solution { public List<List<Integer>> generate(int numRows) { List<List<Integer>> a = new ArrayList<List<Integer>>(); for(int i=0; i<numRows; i++) { List<Integer> row = new ArrayList<Integer>(); for(int j=0; j <= i; j++) { if(j==0 || j==i) { row.add(1); } else { row.add(a.get(i-1).get(j-1) + a.get(i-1).get(j)); } } a.add(row); } return a; } }
4、杨辉三角II
给定一个非负索引 rowIndex，返回「杨辉三角」的第 rowIndex 行。
在「杨辉三角」中，每个数是它左上方和右上方的数的和。
示例 1:
输入: rowIndex = 3
输出: [1,3,3,1]
示例 2:
输入: rowIndex = 0
输出: [1]
示例 3:
输入: rowIndex = 1
输出: [1,1]
提示:
0 <= rowIndex <= 33
class Solution { public List<Integer> getRow(int rowIndex) { int [][] a = new int[34][34]; List<Integer> row = new ArrayList<>(); for(int i=0; i<= rowIndex; i++) { for(int j=0; j<=i; j++) { if(j==0 || j==i) { a[i][j] = 1; } else { a[i][j] = a[i-1][j-1] + a[i-1][j]; } } } for(int i=0; i<=rowIndex; i++) { row.add(a[rowIndex][i]); } return row; } }
5、买股票的最佳时机
给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。
示例 1：
输入：[7,1,5,3,6,4]
输出：5
解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。
示例 2：
输入：prices = [7,6,4,3,1]
输出：0
解释：在这种情况下, 没有交易完成, 所以最大利润为 0。
提示：
1 <= prices.length <= 105
0 <= prices[i] <= 104
class Solution { //dp[i]表示在第i天卖出的价值最大值，它等于当天价值减去之前所有天的最小值 int []dp = new int[prices.length]; //用于保存最小值 int small = prices[0]; for(int i=1; i<prices.length; i++) { //如果第i-1天的价值比前面所有天的价值小，那么最小价值更新为prices[i-1] if(prices[i-1] < small) { small = prices[i-1]; } dp[i] = prices[i] - small; } //再找出dp[]中最大值，即为股票的最大价值 int big = dp[0]; for (int i = 1; i < dp.length; i++) { if(dp[i] > big) { big = dp[i]; } } return big; }
