目录
1.斐波那契数列（LeetCode 509）
2.零钱兑换（ LeetCode 322 ）
3.爬楼梯（ LeetCode 70 ）
4.不同路径（ LeetCode 62 ）
5.最长递增子序列（LeetCode 300）
6.编辑距离（LeetCode 72）
1.斐波那契数列（LeetCode 509）
https://leetcode.cn/problems/fibonacci-number/description/
使用常规的递归方法，是自上而下，时间复杂度很高（O（2^n））。
class Solution {public int fib(int n) {if(n==0)return 0;if(n==1)return 1;return fib(n-1)+fib(n-2); }
}使用动态规划，对每项斐波那契数进行保存，减少重复的计算过程。是自下而上的一种方式
class Solution {public int fib(int n) {int[] dp=new int[n+1];if ( n < 2) return n;dp[0]=0;dp[1]=1;for(int i=2;i<=n;i++){dp[i]=dp[i-1]+dp[i-2];}return dp[n];}
}2.零钱兑换（ LeetCode 322 ）
https://leetcode.cn/problems/coin-change/
给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。
计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。
你可以认为每种硬币的数量是无限的。
class Solution {public int coinChange(int[] coins, int amount) {int[] dp=new int[amount+1];Arrays.fill(dp,-1);dp[0]=0;for(int i=1;i<=amount;i++){for(int j=0;j<coins.length;j++){if(coins[j]<=i && dp[i-coins[j]]!=-1){if(dp[i]==-1 || dp[i-coins[j]]+1<dp[i]){dp[i]=dp[i-coins[j]]+1;}}}}return dp[amount];}
}class Solution {public int coinChange(int[] coins, int amount) {// 初始化数组 dp，长度为 amount + 1，因为在 dp 数组中还会存储金额为 0 的情况// dp[i] 表示想要凑齐 i 元需要的最少硬币个数// dp[0] 表示想要凑齐 0 元需要的最少硬币个数// dp[1] 表示想要凑齐 1 元需要的最少硬币个数int[] dp = new int[amount + 1];// 首先将数组 dp 里面的值都初始化为 -1Arrays.fill(dp, -1);// 想要凑齐 0 元的最少硬币个数是 0 个dp[0] = 0;// 依次计算想要凑齐 1 元到 amount 的最少硬币个数是多少for(int i = 1 ; i <= amount ; i++){// 设置一个变量 j ，遍历数组 coinsfor(int j = 0 ; j < coins.length;j++){// 1、如果当前的硬币面值 coins[j] 小于了 i，表示这枚硬币有可能可以拼凑到 i// 2、那么 i - coins[j] 表示面值 coins[j] 的硬币想要拼凑 i 需要那些面值的硬币金额// 3、而 dp[i-coins[j]] 表示想要凑齐 i - coins[j] 元需要的最少硬币个数// 4、如果 dp[i-coins[j]] != -1 ，表示想要凑齐 i - coins[j] 元需要的最少硬币个数有结果if(coins[j] <= i && dp[i-coins[j]] != -1){// 这个时候，对于金额 i 来说// 1、如果它之前还没有找到凑齐 i 元需要的最少硬币个数// 2、如果此时计算的最少硬币个数比之前保存的结果 dp[i] 更小// 那么更新 dp[i]if(dp[i] == -1 || dp[i-coins[j]] + 1 < dp[i]){// 更新 dp[i]// dp[i] 表示想要凑齐 i 元需要的最少硬币个数// 这个时候 dp[i] 为获取面值为 j 的那 1 个硬币// 加上获取面值为 i - coins[j] 最少需要 dp[i - coins[j]] 个硬币dp[i] = dp[i - coins[j]] + 1;}}}}// dp[amount] 表示想要凑齐 amount 元需要的最少硬币个数return dp[amount];}
}3.爬楼梯（ LeetCode 70 ）
https://leetcode.cn/problems/climbing-stairs/description/
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
class Solution {public int climbStairs(int n) {//dp[n]存储每一层台阶的爬法数量//为了让n=0时不越界，保证dp[1]和dp[2]都有值int[] dp=new int[n+2];dp[1]=1;dp[2]=2;for(int i=3;i<=n;i++){dp[i]=dp[i-1]+dp[i-2];}return dp[n];}
}4.不同路径（ LeetCode 62 ）
https://leetcode.cn/problems/unique-paths/description/
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
问总共有多少条不同的路径？
class Solution {public int uniquePaths(int m, int n) {int dp[][]=new int[m][n];dp[0][0]=1;for(int i=0;i<m;i++){dp[i][0]=1;}for(int j=0;j<n;j++){dp[0][j]=1;}for(int i=1;i<m;i++){for(int j=1;j<n;j++){dp[i][j]=dp[i-1][j]+dp[i][j-1];}}return dp[m-1][n-1];}
}5.最长递增子序列（LeetCode 300）
https://leetcode.cn/problems/longest-increasing-subsequence/description/
给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
示例 1：
输入：nums = [10,9,2,5,3,7,101,18] 输出：4 解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。
class Solution {public int lengthOfLIS(int[] nums) {if (nums.length == 0) return 0;int[] dp=new int[nums.length];Arrays.fill(dp,1);dp[0]=1;int max=1;for(int i=1;i<nums.length;i++){for(int j=0;j<i;j++){if(nums[i]>nums[j]){dp[i]=Math.max(dp[i],dp[j]+1);}}max=Math.max(max,dp[i]);}return max;}
}6.编辑距离（LeetCode 72）
给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数 。
你可以对一个单词进行如下三种操作：
- 插入一个字符
- 删除一个字符
- 替换一个字符
示例 1：
输入：word1 = "horse", word2 = "ros" 输出：3 解释： horse -> rorse (将 'h' 替换为 'r') rorse -> rose (删除 'r') rose -> ros (删除 'e')
class Solution {public int minDistance(String word1, String word2) {int m = word1.length();int n = word2.length();int[][] dp = new int[m + 1][n + 1];// 初始化for (int i = 0; i <= m; i++) {dp[i][0] = i;}for (int j = 0; j <= n; j++) {dp[0][j] = j;}// 填充 dp 表for (int i = 1; i <= m; i++) {for (int j = 1; j <= n; j++) {if (word1.charAt(i - 1) == word2.charAt(j - 1)) {dp[i][j] = dp[i - 1][j - 1];} else {dp[i][j] = 1 + Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]);}}}return dp[m][n];}
}