有没有教做帽子的网站,学校教育网站建设,网站开发找哪家,网站备案如何注销文章目录 动态规划入门斐波那契数路径问题整数拆分动态规划在树中的应用 背包问题01背包完全背包 打家劫舍买卖股票的最佳时机#xff08;状态转换#xff09;最长子序列最长公共序列子序列有关#xff08;删除元素#xff09;回文子串 动态规划入门
斐波那契数
力扣相关… 文章目录 动态规划入门斐波那契数路径问题整数拆分动态规划在树中的应用 背包问题01背包完全背包 打家劫舍买卖股票的最佳时机状态转换最长子序列最长公共序列子序列有关删除元素回文子串 动态规划入门
斐波那契数
力扣相关题目 509.斐波那契数 70.爬楼梯 746.使用最小花费爬楼梯
Java代码
class Solution {// 509.斐波那契数public int fib(int n) {if (n 1) return n;int[] dp new int[n 1];dp[0] 0;dp[1] 1;for (int i 2; i n; i ){dp[i] dp[i - 1] dp[i - 2];}return dp[n];}// 70.爬楼梯public int climbStairs(int n) {if (n 1) return 1;if (n 2) return 2;int[] dp new int[n 1];dp[1] 1; dp[2] 2;for (int i 3; i n; i ){dp[i] dp[i - 1] dp[i - 2];}return dp[n];}// 746.使用最小花费爬楼梯public int minCostClimbingStairs(int[] cost) {int n cost.length;if (n 1) return 0;int[] dp new int[n 1];dp[0] 0;dp[1] 0;for (int i 2; i n; i ){dp[i] Math.min(dp[i - 2] cost[i - 2], dp[i - 1] cost[i - 1]);}return dp[n];}
}路径问题
力扣相关题目 62.不同路径 63.不同路径2
Java代码
class Solution {// 62.不同路径public int uniquePaths(int m, int n) {int[][] dp new int[m][n];for (int i 0; i m; i ) dp[i][0] 1;for (int i 0; i n; i ) dp[0][i] 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];}// 63.不同路径2public int uniquePathsWithObstacles(int[][] obstacleGrid) {int m obstacleGrid.length, n obstacleGrid[0].length;if (obstacleGrid[0][0] 1 || obstacleGrid[m - 1][n - 1] 1) return 0;int[][] dp new int[m][n];for (int i 0; i m obstacleGrid[i][0] 0; i ) dp[i][0] 1;for (int i 0; i n obstacleGrid[0][i] 0; i ) dp[0][i] 1;for (int i 1; i m; i ){for (int j 1; j n; j ){if (obstacleGrid[i][j] 1) continue;dp[i][j] dp[i - 1][j] dp[i][j - 1];}}return dp[m - 1][n - 1];}}整数拆分
力扣相关题目 343.整数拆分
Java代码
class Solution {// 343.整数拆分public int integerBreak(int n) {int[] dp new int[n 1];// 初始条件2可以拆成1*11dp[2] 1;for (int i 3; i n; i ){for (int j 1; j i/2; j ){// 可以拆成两个数i-j和j也可以拆成j和dp[i-j]dp[i] Math.max(dp[i], Math.max((i-j)*j,j*dp[i - j]));}}return dp[n];}}动态规划在树中的应用
力扣相关题目 96.不同的二叉搜索树 Java代码
class Solution {// 96.不同的二叉搜索树public int numTrees(int n) {int[] dp new int[n 1];dp[0] 1;for (int i 1; i n; i ){for (int j 1; j i; j ){// 以dp[3]为例// dp[3]元素1为头结点搜索树的数量 元素2为头结点搜索树的数量 // 元素3为头结点搜索树的数量// 元素1为头结点搜索树的数量 右子树有2个元素的搜索树数量 * 左子树有0个元素的搜索树数量// 元素2为头结点搜索树的数量 右子树有1个元素的搜索树数量 * 左子树有1个元素的搜索树数量// 元素3为头结点搜索树的数量 右子树有0个元素的搜索树数量 * 左子树有2个元素的搜索树数量// 所以 dp[3]dp[2] * dp[0] dp[1] * dp[1] dp[0] * dp[2]dp[i] dp[j - 1]*dp[i - j];}}return dp[n];}}背包问题
本篇主要记录01背包和完全背包问题
01背包
你有一个背包最多能容纳的体积是V现在有n个物品第i个物品的体积为 v i v_i vi ,价值为 w i w_i wi,则 (1) 求这个背包至多能装多大价值的物品 (2) 若背包恰好装满求至多能装多大价值的物品
牛客网 【模板】01背包
Java代码
import java.util.Scanner;
import java.util.*;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {public static void main(String[] args) {Scanner in new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的区别while (in.hasNextInt()) { // 注意 while 处理多个 caseint n in.nextInt();int V in.nextInt();int[] weight new int[n];int[] value new int[n];int[] dp new int[V1];for (int i 0; i n; i ){weight[i] in.nextInt();value[i] in.nextInt();}// 外循环遍历物品for (int i 0; i n; i ){// 内循环倒着遍历容量for (int j V; j weight[i]; j --){// 装该物品dp[j - weight[i]] value[i]// 不装该物品dp[j]// 求最大值dp[j] Math.max(dp[j], dp[j - weight[i]] value[i]);}}System.out.println(dp[V]);int[] dp1 new int[V1];Arrays.fill(dp1,Integer.MIN_VALUE);dp1[0] 0;for (int i 0; i n; i ){for (int j V; j weight[i]; j --){dp1[j] Math.max(dp1[j], dp1[j - weight[i]] value[i]);}}if (dp1[V] 0) dp1[V] 0;System.out.println(dp1[V]);}}
}力扣相关题目 416.分割等和子集 1049.最后一块石头的重量II 494.目标和 474.一和零
Java代码
class Solution {// 416.分割等和子集// 数组中找到子集该子集总和为sum/2// 背包容量为sum/2,物品为数组nums物品重量为nums[i]价值也为nums[i]// dp[target] target?public boolean canPartition(int[] nums) {int n nums.length;if (n 2) return false;int sum 0;for(int i 0; i n; i ){sum nums[i];}if (sum % 2 1) return false;int target sum / 2;// 所以该题等价于背包的容量Vtargetsum/2int[] dp new int[target 1];for (int i 0; i n; i ){for (int j target; j nums[i]; j --){dp[j] Math.max(dp[j],dp[j - nums[i]] nums[i]);}}if (dp[target] target) return true;return false;}// 1049.最后一块石头的重量II// 这道题同样是背包容量为sum/2与416.分割等和子集思路一致public int lastStoneWeightII(int[] stones) {int n stones.length;int sum 0;for (int i 0; i n; i ){sum stones[i];}int target sum / 2;int[] dp new int[target 1];for (int i 0; i n; i ){for (int j target; j stones[i]; j --){dp[j] Math.max(dp[j],dp[j - stones[i]] stones[i]);}}return (sum - dp[target]) - dp[target];}// 494.目标和// 容量为(sum target) / 2的背包问题// 与前两个题不一样的是求方案个数// 递归条件一般是dp[j] dp[j - nums[i]]public int findTargetSumWays(int[] nums, int target) {int n nums.length;int sum 0;for (int i 0; i n; i ){sum nums[i];}if ((sum target) % 2 ! 0) return 0;if (Math.abs(target) sum) return 0;int t (sum target) / 2;if (t 0) t -t;int[] dp new int[t 1];dp[0] 1;for (int i 0; i n; i ){for (int j t; j nums[i]; j --){dp[j] dp[j - nums[i]];}}return dp[t];}// 494.一和零// 之前的题目背包容量是一维的即target// 该题目背包容量为二维的即m与n需要二维数组dppublic int findMaxForm(String[] strs, int m, int n) {int[][] dp new int[m 1][n 1];int oneNum, zeroNum;// 遍历物品strs数组for(String str:strs){// oneNum和zeroNum为物品的重量oneNum 0;zeroNum 0;for (int i 0; i str.length(); i ){if (str.charAt(i) 0) zeroNum ;else oneNum ;}// 遍历背包容量for(int i m; i zeroNum; i --){for (int j n; j oneNum; j --){dp[i][j] Math.max(dp[i][j], dp[i-zeroNum][j-oneNum] 1);}}}return dp[m][n];}}完全背包
你有一个背包最多能容纳的体积是V现在有n个物品每种物品有任意多个第i个物品的体积为 v i v_i vi ,价值为 w i w_i wi,则 (1) 求这个背包至多能装多大价值的物品 (2) 若背包恰好装满求至多能装多大价值的物品
牛客网 【模板】完全背包
代码和01背包的区别为在于遍历背包容量 1.01背包倒序遍历
for (int j V; j weight[i]; j --)
{dp[j] Math.max(dp[j], dp[j - weight[i]] value[i]);
}2.完全背包顺序遍历
for (int j weight[i]; j V; j )
{dp[j] Math.max(dp[j], dp[j - weight[i]] value[i]);
}Java代码
import java.util.Scanner;
import java.util.*;// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {public static void main(String[] args) {Scanner in new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的区别while (in.hasNextInt()) { // 注意 while 处理多个 caseint n in.nextInt();int V in.nextInt();int[] weight new int[n];int[] value new int[n];int[] dp new int[V1];for (int i 0; i n; i ){weight[i] in.nextInt();value[i] in.nextInt();}for (int i 0; i n; i ){// 这个地方与01背包不同for (int j weight[i]; j V; j ){dp[j] Math.max(dp[j], dp[j - weight[i]] value[i]);}}System.out.println(dp[V]);int[] dp1 new int[V1];Arrays.fill(dp1,Integer.MIN_VALUE);dp1[0] 0;for (int i 0; i n; i ){for (int j weight[i]; j V; j ){dp1[j] Math.max(dp1[j], dp1[j - weight[i]] value[i]);if (dp1[j] 0){dp1[j] Integer.MIN_VALUE;}}} System.out.println(dp1[V] Integer.MIN_VALUE ? 0: dp1[V]);}}
}力扣相关题目 518.零钱兑换II 322.零钱兑换 279.完全平方数 377. 组合总和 Ⅳ 139.单词拆分
Java代码
class Solution {// 518.零钱兑换II// 求组合数问题dp[j] dp[j - coins[i]];public int change(int amount, int[] coins) {int[] dp new int[amount 1];dp[0] 1;for (int i 0; i coins.length; i ){for (int j coins[i]; j amount; j ){dp[j] dp[j - coins[i]];}}return dp[amount];}// 322.零钱兑换// 这次不是求最大值而是求最小值// 在初始化是需要Integer.MAX_VALUE填充public int coinChange(int[] coins, int amount) {int maxn Integer.MAX_VALUE;int n coins.length;int[] dp new int[amount 1];Arrays.fill(dp,maxn);dp[0] 0;for (int i 0; i n; i ){for (int j coins[i]; j amount; j ){if (dp[j - coins[i]] ! maxn) dp[j] Math.min(dp[j], dp[j - coins[i]] 1);}}return dp[amount] maxn ? -1:dp[amount];}// 279.完全平方数public int numSquares(int n) {int maxn Integer.MAX_VALUE;int[] dp new int[n 1];Arrays.fill(dp,maxn);dp[0] 0;for (int i 1; i*i n; i ){for (int j i*i; j n; j ){if (dp[j - i*i] ! maxn) dp[j] Math.min(dp[j], dp[j - i*i] 1);}}return dp[n] maxn ? -1 : dp[n];}// 377. 组合总和 Ⅳ// 求排列有顺序的不是组合// 先遍历容量public int combinationSum4(int[] nums, int target) {int n nums.length;int[] dp new int[target 1];dp[0] 1;for (int i 0; i target; i ){for (int j 0; j n; j ){if (i nums[j]) dp[i] dp[i - nums[j]];}}return dp[target];}// 139.单词拆分public boolean wordBreak(String s, ListString wordDict) {int n s.length();boolean[] dp new boolean[n 1];dp[0] true;for (int i 1; i n; i ){for (String word:wordDict){int len word.length();if (i len dp[i - len] word.equals(s.substring(i - len,i))) dp[i] true;}}return dp[n];}}背包总结 递推公式 问能否能装满背包或者最多装多少dp[j] max(dp[j], dp[j - nums[i]] nums[i]) 416.分割等和子集1049.最后一块石头的重量II 问装满背包有几种方法dp[j] dp[j - nums[i]] 494.目标和518.零钱兑换II377. 组合总和 Ⅳ 问背包装满最大价值dp[j] max(dp[j], dp[j - weight[i]] value[i]); 474.一和零 问装满背包所有物品的最小个数dp[j] min(dp[j - coins[i]] 1, dp[j]); 322.零钱兑换279.完全平方数 组合or排列 组合外循环物品内循环容量 518.零钱兑换II 排列外循环容量内循环物品 377. 组合总和 Ⅳ
打家劫舍
力扣相关题目 198.打家劫舍 213.打家劫舍II 337.打家劫舍 III
Java代码
class Solution {// 198.打家劫舍// 一个数组相邻之间不能连着偷如何偷才能得到最大金钱public int rob(int[] nums) {if (nums null || nums.length 0) return 0;if (nums.length 1) return nums[0];int n nums.length;int[] dp new int[n];dp[0] nums[0];dp[1] Math.max(nums[0],nums[1]);for (int i 2; i n; i ){dp[i] Math.max(dp[i - 2] nums[i], dp[i - 1]);}return dp[n - 1];}// 213.打家劫舍II// 数组成环了然后相邻的不能连着偷// 情况一考虑包含首元素不包含尾元素// 情况二考虑包含尾元素不包含首元素// 两种情况求最大public int robRange(int[] nums, int start, int end){if (start end) return nums[start];int[] dp new int[nums.length];dp[start] nums[start];dp[start 1] Math.max(nums[start], nums[start 1]);for (int i start 2; i end; i){dp[i] Math.max(dp[i - 2] nums[i], dp[i - 1]);}return dp[end];}// 337.打家劫舍 III// 采用后序遍历// 如果是偷当前节点那么左右孩子就不能偷val1 cur-val left[0] right[0];// 如果不偷当前节点那么左右孩子就可以偷至于到底偷不偷一定是选一个最大的所以val2 max(left[0], left[1]) max(right[0], right[1]);// 最后当前节点的状态就是{val2, val1}; 即{不偷当前节点得到的最大金钱偷当前节点得到的最大金钱}public int rob(int[] nums) {if (nums null || nums.length 0) return 0;if (nums.length 1) return nums[0];int n nums.length;int result1 robRange(nums,0,n - 2);int result2 robRange(nums,1,n - 1);return Math.max(result1,result2);}public int[] robTree(TreeNode root){if (root null) return new int[]{0,0};int[] left robTree(root.left);int[] right robTree(root.right);int var1 root.val left[0] right[0];int var2 Math.max(left[0],left[1]) Math.max(right[0],right[1]);return new int[] {var2,var1};}public int rob(TreeNode root) {int[] result robTree(root);return Math.max(result[0],result[1]);}}买卖股票的最佳时机状态转换
力扣相关题目 121. 买卖股票的最佳时机 122.买卖股票的最佳时机II 123.买卖股票的最佳时机III 188.买卖股票的最佳时机IV 309.最佳买卖股票时机含冷冻期 714.买卖股票的最佳时机含手续费
Java代码
class Solution {// 121. 买卖股票的最佳时机// dp[i][0]表示第i天持有股票所得最多现金// dp[i][1]表示第i天不持有股票所得最多现金// 如果第i天持有股票即dp[i][0] 那么可以由两个状态推出来// 1.第i-1天就持有股票那么就保持现状所得现金就是昨天持有股票的所得现金 即dp[i - 1][0]// 2.第i天买入股票所得现金就是买入今天的股票后所得现金即-prices[i]// dp[i][0] max(dp[i - 1][0], -prices[i]);// 如果第i天不持有股票即dp[i][1] 也可以由两个状态推出来// 1.第i-1天就不持有股票那么就保持现状所得现金就是昨天不持有股票的所得现金 即dp[i - 1][1]// 2.第i天卖出股票所得现金就是按照今天股票价格卖出后所得现金即prices[i] dp[i - 1][0]// dp[i][1] max(dp[i - 1][1], prices[i] dp[i - 1][0]);public int maxProfit(int[] prices) {int n prices.length;if (n 0) return 0;int[][] dp new int[n][2];dp[0][0] - prices[0];dp[0][1] 0;for (int i 1; i n; i ){dp[i][0] Math.max(dp[i - 1][0], -prices[i]);dp[i][1] Math.max(dp[i - 1][1], dp[i - 1][0] prices[i]);}return dp[n - 1][1];}// 122.买卖股票的最佳时机IIpublic int maxProfit(int[] prices) {int n prices.length;if (n 0) return 0;int[][] dp new int[n][2];dp[0][0] - prices[0];dp[0][1] 0;for (int i 1; i n; i ){// 与上题的区别只在这里dp[i][0] Math.max(dp[i - 1][0], dp[i - 1][1] - prices[i]);dp[i][1] Math.max(dp[i - 1][1], dp[i - 1][0] prices[i]);}return dp[n - 1][1];}// 123.买卖股票的最佳时机III// dp有五个状态// 0.没有操作 其实我们也可以不设置这个状态// 1.第一次持有股票// 2.第一次不持有股票// 3.第二次持有股票// 4.第二次不持有股票public int maxProfit(int[] prices) {int n prices.length;if (n 0) return 0;int[][] dp new int[n][5];dp[0][1] - prices[0];dp[0][3] - prices[0];for (int i 1; i n; i ){dp[i][0] dp[i - 1][0];dp[i][1] Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);dp[i][2] Math.max(dp[i - 1][2], dp[i - 1][1] prices[i]);dp[i][3] Math.max(dp[i - 1][3], dp[i - 1][2] - prices[i]);dp[i][4] Math.max(dp[i - 1][4], dp[i - 1][3] prices[i]);}return dp[n - 1][4];}// 188.买卖股票的最佳时机IV// 上一题拓展到通用的k个股票public int maxProfit(int k, int[] prices) {int n prices.length;if (n 0) return 0;int[][] dp new int[n][2*k 1];for (int i 1; i 2*k; i 2){dp[0][i] - prices[0];}for (int i 1; i n; i ){for (int j 0; j 2*k - 1; j 2 ){dp[i][j 1] Math.max(dp[i - 1][j 1], dp[i - 1][j] - prices[i]);dp[i][j 2] Math.max(dp[i - 1][j 2], dp[i - 1][j 1] prices[i]);}}return dp[n - 1][2*k];}// 309.最佳买卖股票时机含冷冻期// 需要结合状态转换图来理解public int maxProfit(int[] prices) {int n prices.length;if (n 0) return 0;int[][] dp new int[n][4];dp[0][0] - prices[0];for (int i 1; i n; i ){dp[i][0] Math.max(dp[i - 1][0], Math.max(dp[i - 1][1] - prices[i], dp[i - 1][3] - prices[i]));dp[i][1] Math.max(dp[i - 1][1], dp[i - 1][3]);dp[i][2] dp[i - 1][0] prices[i];dp[i][3] dp[i - 1][2];}return Math.max(dp[n - 1][1], Math.max(dp[n - 1][2], dp[n - 1][3]));}// 714.买卖股票的最佳时机含手续费//与122类似就是多了手续费public int maxProfit(int[] prices, int fee) {int n prices.length;if (n 0) return 0;int[][] dp new int[n][2];dp[0][0] - prices[0];for (int i 1; i n; i ){dp[i][0] Math.max(dp[i - 1][0], dp[i - 1][1] - prices[i]);// 卖出需要手续费dp[i][1] Math.max(dp[i - 1][1], dp[i - 1][0] prices[i] - fee);}return Math.max(dp[n - 1][0], dp[n - 1][1]);}}最长子序列
力扣相关题目 300.最长递增子序列 674. 最长连续递增序列 53. 最大子序和 718. 最长重复子数组
Java代码
class Solution {// 300.最长递增子序列// dp[i]: 表示i之前包括i的以nums[i]结尾的最长递增子序列的长度// 位置i的最长升序子序列等于j从0到i-1各个位置的最长升序子序列 1 的最大值// if (nums[i] nums[j]) dp[i] max(dp[i], dp[j] 1)// 最后求全局的最大值public int lengthOfLIS(int[] nums) {int n nums.length;if (n 1) return n;int[] dp new int[n];Arrays.fill(dp,1);for (int i 1; i n; i ){for (int j 0; j i; j ){if (nums[j] nums[i]) dp[i] Math.max(dp[i], dp[j] 1);}}int res 0;for (int i 0; i n; i ){res Math.max(res, dp[i]);}return res;}// 674. 最长连续递增序列// dp[i]:以下标i为结尾的连续递增的子序列长度// 以 i 为结尾的连续递增的子序列长度 一定等于 以i - 1为结尾的连续递增的子序列长度 1// dp[i] dp[i - 1] 1 与上题的区别public int findLengthOfLCIS(int[] nums) {int n nums.length;if (n 0) return 0;int res 1;int[] dp new int[n];Arrays.fill(dp,1);for (int i 1; i n; i ){if (nums[i] nums[i - 1]) dp[i] dp[i - 1] 1;if (res dp[i]) res dp[i];}return res;}// 53. 最大子序和// dp[i]两个方面// 1.dp[i - 1] nums[i]即nums[i]加入当前连续子序列和// 2.nums[i]即从头开始计算当前连续子序列和// 取最大值public int maxSubArray(int[] nums) {int n nums.length;if (n 0) return 0;int[] dp new int[n];dp[0] nums[0];int result dp[0];for (int i 1; i n; i ){dp[i] Math.max(dp[i - 1] nums[i], nums[i]);if (dp[i] result) result dp[i];}return result;}// 718. 最长重复子数组// dp[i][j] 以下标i - 1为结尾的A和以下标j - 1为结尾的B最长重复子数组长度为dp[i][j]// 与674很像public int findLength(int[] nums1, int[] nums2) {int n nums1.length, m nums2.length;int[][] dp new int[n][m];for (int i 0; i n; i ) {if (nums1[i] nums2[0]) dp[i][0] 1;}for (int j 0; j m; j ){if (nums2[j] nums1[0]) dp[0][j] 1;}int res 0;for (int i 0; i n; i ){for (int j 0; j m; j ){if (nums1[i] nums2[j] i 0 j 0){dp[i][j] dp[i - 1][j - 1] 1;}if (dp[i][j] res) res dp[i][j];}}return res;}}最长公共序列
力扣相关题目 1143.最长公共子序列 1035.不相交的线
Java代码
class Solution {// 1143.最长公共子序列// dp[i][j]长度为[0, i - 1]的字符串text1与长度为[0, j - 1]的字符串text2的最长公共子序列为dp[i][j]// 两种情况// 1. 如果text1[i - 1] 与 text2[j - 1]相同那么找到了一个公共元素所以dp[i][j] dp[i - 1][j - 1] 1;// 2.如果text1[i - 1] 与 text2[j - 1]不相同那就看看text1[0, i - 2]与text2[0, j - 1]的最长公共子序列 和 text1[0, i - 1]与text2[0, j - 2]的最长公共子序列取最大的public int longestCommonSubsequence(String text1, String text2) {int m text1.length(), n text2.length();int[][] dp new int[m1][n1];for (int i 1; i m; i ){for (int j 1; j n; j ){if (text1.charAt(i - 1) text2.charAt(j - 1)){dp[i][j] dp[i - 1][j - 1] 1;}else{dp[i][j] Math.max(dp[i - 1][j], dp[i][j - 1]);}}}return dp[m][n];}// 1035.不相交的线// 与上一题等价public int maxUncrossedLines(int[] nums1, int[] nums2) {int n nums1.length, m nums2.length;int[][] dp new int[n 1][m 1];for (int i 1; i n; i ){for (int j 1; j m; j ){if (nums1[i - 1] nums2[j - 1]){dp[i][j] dp[i - 1][j - 1] 1;}else{dp[i][j] Math.max(dp[i - 1][j], dp[i][j - 1]);}}}return dp[n][m];}}子序列有关删除元素
力扣相关题目 392.判断子序列 115.不同的子序列 583. 两个字符串的删除操作 72. 编辑距离
Java代码
class Solution {// 392.判断子序列// dp[i][j] 表示以下标i-1为结尾的字符串s和以下标j-1为结尾的字符串t相同子序列的长度// s[i - 1] t[j - 1]t中找到了一个字符在s中也出现了// s[i - 1] ! t[j - 1]相当于t要删除元素继续匹配public boolean isSubsequence(String s, String t) {int n s.length(), m t.length();int[][] dp new int[n 1][m 1];for (int i 1; i n; i ){for (int j 1; j m; j ){if (s.charAt(i - 1) t.charAt(j - 1)){dp[i][j] dp[i - 1][j - 1] 1;}else{dp[i][j] dp[i][j - 1];}}}if (dp[n][m] n) return true;return false;}// 115.不同的子序列// dp[i][j]以i-1为结尾的s子序列中出现以j-1为结尾的t的个数为dp[i][j]// s[i - 1] t[j - 1]:// 1.一部分是用s[i - 1]来匹配那么个数为dp[i - 1][j - 1]。即不需要考虑当前s子串和t子串的最后一位字母所以只需要 dp[i-1][j-1]// 2.一部分是不用s[i - 1]来匹配个数为dp[i - 1][j]// s[i - 1] ! t[j - 1]不用s[i - 1]来匹配就是模拟在s中删除这个元素public int numDistinct(String s, String t) {int n s.length(), m t.length();int[][] dp new int[n 1][m 1];for (int i 0; i n; i ) dp[i][0] 1;for (int j 1; j m; j ) dp[0][j] 0;for (int i 1; i n; i ){for (int j 1; j m; j ){if (s.charAt(i - 1) t.charAt(j - 1)){dp[i][j] dp[i - 1][j - 1] dp[i - 1][j];}else dp[i][j] dp[i - 1][j];}}return dp[n][m];}// 583. 两个字符串的删除操作// dp[i][j]以i-1为结尾的字符串word1和以j-1位结尾的字符串word2// s[i - 1] t[j - 1]:dp[i][j] dp[i - 1][j - 1];// s[i - 1] ! t[j - 1]删除s的或t的public int minDistance(String word1, String word2) {int n word1.length(), m word2.length();int[][] dp new int[n 1][m 1];for (int i 0; i n; i ) dp[i][0] i;for (int j 0; j m; j ) dp[0][j] j;for (int i 1; i n; i ){for (int j 1; j m; j ){if (word1.charAt(i - 1) word2.charAt(j - 1)){dp[i][j] dp[i - 1][j - 1];}else{dp[i][j] Math.min(dp[i - 1][j] 1, dp[i][j - 1] 1);}}}return dp[n][m];}// 72. 编辑距离// 删除或添加可以都看作是删除// word1替换word1[i - 1]使其与word2[j - 1]相同public int minDistance(String word1, String word2) {int n word1.length(), m word2.length();int[][] dp new int[n 1][m 1];for (int i 0; i n; i ) dp[i][0] i;for (int j 1; j m; j ) dp[0][j] j;for (int i 1; i n; i ){for (int j 1; j m; j ){if (word1.charAt(i - 1) word2.charAt(j - 1)){dp[i][j] dp[i - 1][j - 1];}else{dp[i][j] Math.min(dp[i - 1][j - 1], Math.min(dp[i - 1][j], dp[i][j - 1]))1;}}}return dp[n][m];}}回文子串
力扣相关题目 647. 回文子串 516.最长回文子序列
Java代码
class Solution {// 647. 回文子串// 只考虑s[i] t[j]的情况// 1.下标i 与 j相同同一个字符例如a当然是回文子串// 2.下标i 与 j相差为1例如aa也是回文子串// 3.下标i 与 j相差大于1的时候例如cabac此时s[i]与s[j]已经相同了我们看i到j区间是不是回文子串就看aba是不是回文就可以了那么aba的区间就是 i1 与 j-1区间这个区间是不是回文就看dp[i 1][j - 1]是否为true。public int countSubstrings(String s) {int n s.length();boolean[][] dp new boolean[n][n];int res 0;for (int i 0; i n; i ){for (int j 0; j n; j ){dp[i][j] false;}}for (int i n - 1; i 0; i --){for (int j i; j n; j ){if (s.charAt(i) s.charAt(j)){if (j - i 1){res ;dp[i][j] true;}else if (dp[i 1][j - 1]){res ;dp[i][j] true;}}}}return res;}// 516.最长回文子序列// 如果s[i]与s[j]不相同说明s[i]和s[j]的同时加入 并不能增加[i,j]区间回文子序列的长度那么分别加入s[i]、s[j]看看哪一个可以组成最长的回文子序列public int longestPalindromeSubseq(String s) {int n s.length();int[][] dp new int[n][n];for (int i 0; i n; i ) dp[i][i] 1;for (int i n - 1; i 0; i --){for (int j i 1; j n; j ){if (s.charAt(i) s.charAt(j)){dp[i][j] dp[i 1][j - 1] 2;}else{dp[i][j] Math.max(dp[i 1][j], dp[i][j - 1]);}}}return dp[0][n - 1];}}
