leetcode编码解析（1）动态规划以及Java内置排序
目录
动态规划
斐波那契数
第N个斐波那契
使用最小花费爬楼梯
灵神题解：
1.记忆化搜索
2.动态规划
3.化简
Java内置排序算法
数组排序
Arrays.sort()
使用sort实现倒序
对对象数组实现排序 :
对字符串数组实现倒序排序：
List集合排序
Collections.reverse()
动态规划
爬楼梯
70. 爬楼梯
https://leetcode.cn/problems/climbing-stairs/
class Solution { public int climbStairs(int n) { int p = 1； int q = 2; if(n == 1) return p; else if(n == 2) return q; else return { for(int i = 3;i<=n;i++){ r = q+p; p = q; q = r; } return r; } }}思路：第一级选择走1格 第二级选择走2格
动态数组滚动（从第三格）r = p+q 第三格是前两格的方法数（选择走1格还是2格）
斐波那契数
509. 斐波那契数https://leetcode.cn/problems/fibonacci-number/
class Solution { public int fib(int n) { if(n == 0) return 0; else if(n == 1) return 1; else return fib(n-1) + fib(n-2); }}同上
第N个斐波那契
1137. 第 N 个泰波那契数https://leetcode.cn/problems/n-th-tribonacci-number/
class Solution { public int tribonacci(int n) { if(n == 0) return 0; if(n <= 2) return 1; int p = 0, q = 0, r = 1, s = 1; for (int i = 3; i <= n; ++i) { p = q; q = r; r = s; s = p + q + r; } return s; }}使用最小花费爬楼梯
746. 使用最小花费爬楼梯https://leetcode.cn/problems/min-cost-climbing-stairs/
class Solution { public int minCostClimbingStairs(int[] cost) { int n = cost.length; //创建dp数组 int[] dp = new int[n+1]; dp[0] = dp[1] = 0; for(int i = 2;i<= n;i++){ dp[i] = Math.min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]); } return dp[n]; }}设置dp动态数组存每一步的数值 并且规划最小的数字
打家劫舍
198. 打家劫舍https://leetcode.cn/problems/house-robber/
灵神题解：
1.记忆化搜索
class Solution { private int[] nums,memo; public int rob(int[] nums) { this.nums = nums; int n = nums.length; memo = new int[n]; Arrays.fill(memo,-1); return dfs(n-1); } private int dfs(int i){ if(i < 0){ return 0; } if(memo[i]!=-1){ return memo[i]; } int res = Math.max(dfs(i-1),nums[i]+dfs(i-2)); memo[i] = res; return res; }}1. 记忆化搜索：将数组全赋值-1 代表没有搜索过
memo：记忆化数组
Math.max(dfs(i-1),nums[i]+dfs(i-2));
int res = Math.max(dfs(i-1),nums[i]+dfs(i-2)); 对于i-1,i-2个元素可以选择选不偷或者偷
2.动态规划
class Solution { public int rob(int[] nums) { int n = nums.length; int[] a = new int[n+2]; for(int i = 0;i<n;i++){ a[i+2] = Math.max(a[i+1],a[i]+nums[i]); } return a[n+1]; }}3.化简
private int rob(int[] nums) { int f0 = 0; int f1 = 0; for (int x : nums) { int newF = Math.max(f1, f0 + x); f0 = f1; f1 = newF; } return f1; }Java内置排序算法
数组排序
Arrays.sort()
import java.util.Arrays; public class Main { public static void main(String[] args) { int[] arr = {5, 2, 9, 1, 5, 6}; // 对基本类型数组排序（使用双轴快速排序） Arrays.sort(arr); System.out.println(Arrays.toString(arr)); // [1, 2, 5, 5, 6, 9] // 对对象数组排序（使用归并排序的变体） Integer[] objArr = {5, 2, 9, 1, 5, 6}; Arrays.sort(objArr); System.out.println(Arrays.toString(objArr)); // [1, 2, 5, 5, 6, 9] }}注:基本类型排序双轴快速排序
对象数组排序 归并排序
使用sort实现倒序
对对象数组实现排序 :
Arrays.sort(integerArray, (a, b) -> b - a);对字符串数组实现倒序排序：
Arrays.sort(stringArray, (a, b) -> b.compareTo(a));List集合排序
import java.util.ArrayList;import java.util.Collections;import java.util.List;public class Main { public static void main(String[] args) { List list = new ArrayList(); list.add(5); list.add(2); list.add(9); list.add(1); Collections.sort(list); System.out.println(list); // [1, 2, 5, 9] }}倒序
Collections.reverse()
public class ReverseArray { public static void main(String[] args) { Integer[] arr = {1, 2, 3, 4, 5}; // 注意：必须是对象数组，不能是基本类型数组 // 倒序前 System.out.println(\"原始数组: \" + Arrays.toString(arr)); // 使用 Collections.reverse() List list = Arrays.asList(arr); Collections.reverse(list); // 倒序后 System.out.println(\"倒序后数组: \" + list); }}
