动态规划【Lecode_HOT100】

1.爬楼梯No.70

class Solution {public int climbStairs(int n) {if (n == 1) {return 1;}// 初始化dp数组int[] dp = new int[n + 1];dp[0] = 1; // 基本情况dp[1] = 1; // 基本情况// 填充dp数组for (int i = 2; i <= n; i++) {dp[i] = dp[i - 1] + dp[i - 2];  // 当前阶梯的方法数等于从前一阶或前两阶到达的总方法数}return dp[n]; // 返回到达n阶的方法数}
}

2.杨辉三角No.118

class Solution {public List<List<Integer>> generate(int numRows) {List<List<Integer>> triangle = new ArrayList<>();for (int row = 0; row < numRows; row++) {List<Integer> currentRow = new ArrayList<>();// 每一行的第一个元素是 1currentRow.add(1);// 计算当前行的中间元素for (int col = 1; col < row; col++) {List<Integer> prevRow = triangle.get(row - 1);int value = prevRow.get(col - 1) + prevRow.get(col);currentRow.add(value);}// 每一行的最后一个元素是 1（除了第一行）if (row > 0) {currentRow.add(1);}// 将当前行添加到三角形中triangle.add(currentRow);}  return triangle;}
}

3.打家劫舍No.198

class Solution {public int rob(int[] nums) {if (nums == null || nums.length == 0) {return 0;}if (nums.length == 1) {return nums[0];}// dp[i] 表示偷窃到第 i 间房屋时的最大金额int[] dp = new int[nums.length];dp[0] = nums[0]; // 第 0 间房屋的最大金额就是 nums[0]dp[1] = Math.max(nums[0], nums[1]); // 第一或第二间房屋的最大金额// 从第 2 间房屋开始填充 dp 数组for (int i = 2; i < nums.length; i++) {dp[i] = Math.max(dp[i-1], nums[i] + dp[i-2]);}return dp[nums.length - 1]; // 返回最后一间房屋的最大金额}
}

4.完全平方数No.279

class Solution {public int numSquares(int n) {// 初始化 dp 数组，大小为 n + 1int[] dp = new int[n + 1];// 初始条件 dp[0] = 0dp[0] = 0;// 从 1 到 n 填充 dp 数组for (int i = 1; i <= n; i++) {dp[i] = Integer.MAX_VALUE; // 初始值为一个较大的值for (int j = 1; j * j <= i; j++) {dp[i] = Math.min(dp[i], dp[i - j * j] + 1);}}// 返回 dp[n]，即最少的完全平方数的数量return dp[n];}
}

5.零钱兑换No.322

class Solution {public int coinChange(int[] coins, int amount) {// dp[i] 表示凑成金额 i 的最少硬币数int[] dp = new int[amount + 1];// 初始化 dp 数组Arrays.fill(dp, amount + 1);  // 初始值为一个很大的数dp[0] = 0;  // 凑成 0 金额需要 0 个硬币// 遍历每个金额，从 1 到 amountfor (int i = 1; i <= amount; i++) {// 遍历每种硬币for (int coin : coins) {if (i >= coin) {dp[i] = Math.min(dp[i], dp[i - coin] + 1);}}}// 如果 dp[amount] 还是初始值，说明无法凑成该金额return dp[amount] == amount + 1 ? -1 : dp[amount];}
}

class Solution {public int coinChange(int[] coins, int amount) {int[] res = new int[amount + 1];Arrays.fill(res,Integer.MAX_VALUE);res[0] = 0;for (int i = 1; i <= amount; i++) {for (int coin : coins) {if (i >= coin&&res[i - coin] != Integer.MAX_VALUE)res[i] = Math.min(res[i], res[i - coin] + 1);}}return res[amount] == Integer.MAX_VALUE ? -1 : res[amount];}
}

6.单词拆分No.139

import java.util.List;
import java.util.HashSet;class Solution {public boolean wordBreak(String s, List<String> wordDict) {// 将 wordDict 转化为 HashSet，提高查找效率HashSet<String> wordSet = new HashSet<>(wordDict);// 创建 dp 数组，dp[i] 表示字符串 s[0..i-1] 是否可以通过字典拼接出来boolean[] dp = new boolean[s.length() + 1];dp[0] = true;  // 空字符串可以被拼接出来// 遍历每个位置 i，检查是否可以通过字典中的单词拼接出 s[0..i-1]for (int i = 1; i <= s.length(); i++) {for (int j = 0; j < i; j++) {// 如果 dp[j] 为 true，并且 s[j..i-1] 是字典中的单词if (dp[j] && wordSet.contains(s.substring(j, i))) {dp[i] = true;break;  // 一旦找到一个有效的分割，就可以停止内层循环}}}// 返回 dp[s.length()]，如果为 true，说明 s 可以通过字典中的单词拼接出来return dp[s.length()];}
}

7.最长递增子序列No.300

public int lengthOfLIS(int[] nums) {int  n = nums.length;int[] dp = new int[n];Arrays.fill(dp,1);// 每个元素最小的递增子序列长度是 1// 遍历每个元素for(int i = 1;i<n;i++){// 检查前面所有的元素for(int j = 0;j<i;j++){// 如果 nums[i] > nums[j]，可以扩展递增子序列if(nums[j]<nums[i]){dp[i] = Math.max(dp[j]+1,dp[i]);}}}// 返回 dp 数组中的最大值int res=0;for(int i=0;i<n;i++){res=Math.max(res,dp[i]);}return res;}

8.乘积最大子数组No.152

class Solution {public int maxProduct(int[] nums) {if (nums == null || nums.length == 0) {return 0;}int maxProd = nums[0];  // 当前最大乘积int minProd = nums[0];  // 当前最小乘积int result = nums[0];   // 最终结果// 从第二个元素开始for (int i = 1; i < nums.length; i++) {// 如果当前元素是负数，交换 maxProd 和 minProdif (nums[i] < 0) {int temp = maxProd;maxProd = minProd;minProd = temp;}// 更新当前最大乘积和最小乘积maxProd = Math.max(nums[i], maxProd * nums[i]);minProd = Math.min(nums[i], minProd * nums[i]);// 更新最终结果result = Math.max(result, maxProd);}return result;}
}

9.分割等和子集No.416

class Solution {public boolean canPartition(int[] nums) {if(nums == null || nums.length == 0) return false;int n = nums.length;int sum = 0;for(int num : nums) {sum += num;}//总和为奇数，不能平分if(sum % 2 != 0) return false;int target = sum / 2;int[] dp = new int[target + 1];for(int i = 0; i < n; i++) {for(int j = target; j >= nums[i]; j--) {//物品 i 的重量是 nums[i]，其价值也是 nums[i]dp[j] = Math.max(dp[j], dp[j - nums[i]] + nums[i]);}//剪枝一下，每一次完成內層的for-loop，立即檢查是否dp[target] == target，優化時間複雜度（26ms -> 20ms）if(dp[target] == target)return true;}return dp[target] == target;}
}