seo网站建设培训,企业网站搜索优化外,网站开发经济可行性分析,深圳建站推广动态规划509.斐波那契数列70.爬楼梯746.使用最小花费怕楼梯62.不同路径63.不同路径||343.整数拆分96.不同的二叉搜索树01背包问题416.分割等和子集1049.最后一块石头的重量||494.目标和474.一和零完全背包问题518.零钱兑换||377.组合总和IV322.零钱兑换279.完全平方数139.单词拆…
动态规划509.斐波那契数列70.爬楼梯746.使用最小花费怕楼梯62.不同路径63.不同路径||343.整数拆分96.不同的二叉搜索树01背包问题416.分割等和子集1049.最后一块石头的重量||494.目标和474.一和零完全背包问题518.零钱兑换||377.组合总和IV322.零钱兑换279.完全平方数139.单词拆分打家劫舍198.打家劫舍213.打家劫舍||买卖股票121.买卖股票的最佳时机300.最长递增子序列674.最长连续递增序列718.最长重复子数组1143.最长公共子序列1035.不相交的线53.最大子数组和392.判断子序列115.不同的子序列583.两个字符串的删除操作72.编辑距离647.回文子串516.最长回文子序列509.斐波那契数列 思路 用一个数组把每个数字都存起来即可。 public int fib(int n) {if(n0) {return 0;}if(n1) {return 1;}int []dpnew int[n];dp[0]1;dp[1]1;for(int i2;in;i) {dp[i]dp[i-1]dp[i-2];}return dp[n-1];}70.爬楼梯 思路 也是用递推的方法斐波那契数列。 public int climbStairs(int n) {int []dpnew int[n1];if(n1) {return 1;}if(n2) {return 2;}dp[1]1;dp[2]2;for(int i3;in1;i) {dp[i]dp[i-1]dp[i-2];}return dp[n];}746.使用最小花费怕楼梯 思路 当前台阶 的最小花费体力是上一层的最小体力加上跳出上一层需要花费的体力。或者上两层的最小体力加上跳出上两层需要花费的最小体力。这两个取一个最小值。因为题目要求可以从第0阶开始跳也可以从第1阶开始跳所以第0阶和第1阶的初始值为0.
public int minCostClimbingStairs(int[] cost) {int dp[]new int[cost.length1];dp[0]0;dp[1]0;for(int i2;icost.length;i) {dp[i]Math.min(dp[i-1]cost[i-1], dp[i-2]cost[i-2]);}return dp[cost.length];}62.不同路径 思路 首先确定dp[i][j]的含义。 代表从头到达这个点有多少条路径。 然后递推公式dp[i][j]dp[i-1][j]dp[i][j-1]。 初始化首先初始化第一行和第一列方法都是1。 然后调用递推公式即可。 public int uniquePaths(int m, int n) {int dp[][]new int[m][n];//代表要达到这个位置需要多少路径//初始化for(int i0;im;i) {dp[i][0]1;}for(int i0;in;i) {dp[0][i]1;}for(int i1;im;i) {for(int j1;jn;j) {dp[i][j]dp[i-1][j]dp[i][j-1];}}return dp[m-1][n-1];
63.不同路径|| 思路 当遇到没有障碍的时候再初始化如果遇到障碍后边的就不用初始化了。 然后递推公式中如果不遇到障碍再递推如果遇到障碍直接初始化为0即可。
public int uniquePathsWithObstacles(int[][] obstacleGrid) {//初始化。如果遇到有障碍直接停下int mobstacleGrid.length;int nobstacleGrid[0].length;int dp[][]new int[m][n];//如果遇到初始位置和终止位置有障碍直接返回0因为此路就不通了。if(obstacleGrid[0][0]1||obstacleGrid[m-1][n-1]1) {return 0;}//进行初始化当没障碍的时候才进行初始化for(int i0;imobstacleGrid[i][0]0;i) {dp[i][0]1;}for(int i0;inobstacleGrid[0][i]0;i) {dp[0][i]1;}for(int i1;im;i) {for(int j1;jn;j) {dp[i][j](obstacleGrid[i][j]0)?dp[i-1][j]dp[i][j-1]:0;}}return dp[m-1][n-1];}343.整数拆分 思路 dp[i]数组的含义就是i能拆分到的数值的最大值。 所以从3开始迭代。每个数字再进行拆分。 从1开始。看j*(i-j)。j*(dp[i-j]),dp[i]哪个大。dp[i-j]后边就相当于很多数字相乘。 public int integerBreak(int n) {if(n1) {return 0;}if(n2) {return 1;}int dp[]new int[n1];//代表数字i拆分的最大值.//初始化dp[0]0;dp[1]0;dp[2]1;for(int i3;in;i) {for(int j1;ji;j) {dp[i]Math.max(dp[i], Math.max(j*(i-j),j* dp[i-j]));}}return dp[n];}96.不同的二叉搜索树 思路 大的节点都是由小的节点推出来的。让1到i分别做根节点然后生成树的种类是左子树的种类乘以右子树的种类。 public int numTrees(int n) {int dp[]new int[n1];//代表n个节点组成的有多少个情况//初始化dp[0]1;dp[1]1;for(int i2;in;i) {for(int j1;ji;j) {//j代表j作为根节点的情况那么左子树有j-1个节点右子树有i-j个节点dp[i]dp[j-1]*dp[i-j];}}return dp[n];}01背包问题
416.分割等和子集 思路 转换成背包问题就是当这个背包装的容量最大时能不能满足target的目标值。
先遍历物品再遍历背包。遍历背包的时候要从后往前遍历因为下一层的时候可能要用到左上角的值。注意dp数组的含义
public boolean canPartition(int[] nums) {//判断有没有满足平分的数组if(numsnull||nums.length0) {return false;}int sum0;for(int num:nums) {sumnum;}if(sum%21) {return false;//如果是奇数的话肯定是不能平分的}int targetsum/2;int []dpnew int[target1];//dp数组代表当前容量所能装的最大值for(int i0;inums.length;i) {//先遍历物品再遍历背包for(int jtarget;jnums[i];j--) {dp[j]Math.max(dp[j], dp[j-nums[i]]nums[i]);}}return dp[target]target;}1049.最后一块石头的重量|| 思路 将石头尽量分成大小相等的两堆然后分配一个sum/2的容量的背包去装石头这样遍历完整个数组后背包里装的是尽可能多的石头。装完了之后让剩下的一堆石头减去这堆石头就是剩余的最小的石头了。 public int lastStoneWeightII(int[] stones) {if(stonesnull||stones.length0) {return 0;}int sum0;for(int stone:stones) {sumstone;}int targetsum/2;int []dpnew int [target1];//dp数组代表当前容量所能装的最大值for(int i0;istones.length;i) {for(int jtarget;jstones[i];j--) {dp[j]Math.max(dp[j],dp[j-stones[i]]stones[i]);}}return sum-dp[target]-dp[target];//将石头分成两堆用大的一堆减去小的一堆} 494.目标和 思路 将整个数组分成正数和负数两部分。 public int findTargetSumWays(int[] nums, int target) {//将数组分成两堆左边是正数右边是负数,则有左右sum左-右target 然后我们就可以求出左边的数 左(sumtarget)/2//左边的数是正数给一个这样大小的背包我们去求有多少种这样的方法可以装满这个背包就是有多少种这样组合的正数可以放在左边//dp[j]的含义。装满j容量大小的背包有dp[j]种方法int sum0;for(int num:nums) {sumnum;}//如果target过大 sum将无法满足if ( target 0 sum -target) return 0;if ((target sum) % 2 ! 0) return 0;int temp(sumtarget)/2;int[] dpnew int[temp1];//递推公式dp[5]dp[4]dp[3]dp[2]dp[1]dp[0] 因为有1的话还有dp[4]种方法以此类推就可以了dp[0]1;for(int i0;inums.length;i) {//先遍历物品for(int jtemp;jnums[i];j--) {dp[j]dp[j-nums[i]];}}return dp[temp];}474.一和零 思路 这道题的背包变成二维的了。 背包容量有m个0和n个1. 需要统计出每个字符串包含的0和1的个数。然后再去迭代。
public int findMaxForm(String[] strs, int m, int n) {int dp[][]new int[m1][n1];//dp代表当前背包的容量能最多能放多少个含x个0y个1的元素。m1n1代表二维数组的容量int zeronum;int onenum;for(String str:strs) {zeronum0;onenum0;for(char c:str.toCharArray()) {if(c0) {zeronum;}else if(c1) {onenum;}}for(int im;izeronum;i--) {for(int jn;jonenum;j--) {dp[i][j]Math.max(dp[i-zeronum][j-onenum]1,dp[i][j] );}}}return dp[m][n];}完全背包问题
518.零钱兑换|| 思路 已经给了你背包容量的大小这里只不过是一个物品可以被装很多次背包从小到大遍历就行了。前提是容量得等于当前硬币的大小。 public int change(int amount, int[] coins) {//递推表达式int[] dp new int[amount 1];//初始化dp数组表示金额为0时只有一种情况也就是什么都不装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];}377.组合总和IV 思路 这道题要强调元素的顺序。所以先遍历背包再遍历物品。然后如果背包容量大于等于物品的话就把它加进去。 public int combinationSum4(int[] nums, int target) {//因为这个组合强调遍历顺序了所以不同顺序的物品也要算作不同的结果int dp[]new int[target1];//初始化dp[0]1dp[0]1;for(int i0;itarget;i) {//先遍历背包for(int j0;jnums.length;j) {if(inums[j]) {//如果dp[i]dp[i-nums[j]];}}}return dp[target];}322.零钱兑换 思路 要保证最小的数组把数组初始化成最大值然后每次去迭代dp[j]都去选取最小的值。 dp[j]的含义。装满容量为j的背包最小的元素要多少。 public int coinChange(int[] coins, int amount) {int dp[]new int[amount1];//初始化dp数组为最大的值for(int i0;iamount1;i) {dp[i]Integer.MAX_VALUE;}//初始化dp[0]0;for(int i0;icoins.length;i) {//先遍历物品再遍历背包for(int jcoins[i];jamount;j) {//只有dp[j-coins[i]]不是初始最大值时该位才有选择的必要if(dp[j-coins[i]]!Integer.MAX_VALUE) {dp[j]Math.min(dp[j], dp[j-coins[i]]1);}}}return dp[amount]Integer.MAX_VALUE?-1:dp[amount];}279.完全平方数 思路 用完全平方数做物品然后背包容量是目标数大小然后每次更新最小的数就可以了。 public int numSquares(int n) {//生成完全平方数做物品int[] dpnew int[n1];//初始化for(int i0;in;i) {dp[i]Integer.MAX_VALUE;}dp[0]0;for(int i1;i*in;i) {//先遍历物品for(int ji*i;jn;j) {//再遍历背包if(dp[j-(i*i)]!Integer.MAX_VALUE) {dp[j]Math.min(dp[j], dp[j-i*i]1);}}}return dp[n];}139.单词拆分 思路 完全背包问题。将字符串想象成一个背包每个单词是物品。判断物品能不能装满这个背包即可。因为字符串有顺序问题。所以是排列问题先遍历背包。再遍历物品。判断ji之间的字符串在不在物品里边即可。 dp[0]初始化为true其他初始化为false。 public boolean wordBreak(String s, ListString wordDict) {HashSetString setnew HashSet(wordDict);boolean[] valid new boolean[s.length() 1];valid[0] true;for (int i 1; i s.length(); i) {for (int j 0; j i !valid[i]; j) {if (set.contains(s.substring(j, i)) valid[j]) {valid[i] true;}}}return valid[s.length()];}打家劫舍
198.打家劫舍 思路 确定dp数组含义dp[i]表示从下标i以前所能偷得的最大金币数。 初始化dp[0]和dp[1]。 然后i需要从前两个位置来确定偷还是不偷这两个状态中去取一个最大值。 public int rob(int[] nums) {if(nums.length1) {return nums[0];}int []dpnew int[nums.length];//dp[]数组含义偷到dp[i]的时候所能偷的最大数量//初始化dp[0]nums[0];//只能偷一个的话肯定是当前的最大值dp[1]Math.max(nums[0], nums[1]);//偷两个元素的话是偷前两个元素的最大值for(int i2;inums.length;i) {dp[i]Math.max(dp[i-2]nums[i], dp[i-1]);//当前的结果是偷i的结果还是不偷i的结果}return dp[nums.length-1];}213.打家劫舍|| 思路 这道题就是在打家劫舍的基础上判断有没有环可以分两种情况来考虑第一种情况就是考虑第一个元素第二种情况就是考虑最后一个元素。然后这两种情况取一个最大值。 public int rob(int[] nums) {if (nums null || nums.length 0)return 0;int len nums.length;if (len 1)return nums[0];return Math.max(robAction(nums, 0, len - 1), robAction(nums, 1, len));}int robAction(int[] nums, int start, int end) {int x 0, y 0, z 0;for (int i start; i end; i) {y z;z Math.max(y, x nums[i]);x y;}return z;}买卖股票
121.买卖股票的最佳时机 思路 定义两个状态一个是持有股票的状态一个是不持有股票的状态这两个状态都可以通过前一天推出来。 然后找到不持有股票状态的最大值即可 public int maxProfit(int[] prices) {//dp数组含义dp[i][0]表示持有股票的最大金钱持有股票不代表就是这天买的也可能是前几天买的//dp[i][1]表示不持有股票的最大金钱卖出股票不代表就是这天卖的也可能是前几天卖的int [][]dpnew int[prices.length][2];//dp数组初始化dp[0][0]-prices[0];//持有股票的最大金钱就是这天卖的dp[0][1]0;//表示不持有股票的最大金钱for(int i1;iprices.length;i) {dp[i][0]Math.max(dp[i-1][0], -prices[i]);//可能是前几天就买了也可能是当天买的dp[i][1]Math.max(dp[i-1][1], dp[i][0]prices[i]);//可能是当天卖的}return dp[prices.length-1][1];}300.最长递增子序列 思路 从第二个数字开始遍历然后里边再套一层循环从i之前的元素开始。如果当前的字母比前边的数字大。那么就取一个最大值。最后输出数组里边的最大值即可。 public static int lengthOfLIS(int[] nums) {//dp数组定义dp[i]以i为结尾的最长递增子序列的最大值int []dpnew int[nums.length];//初始化Arrays.fill(dp,1);dp[0]1;for(int i1;inums.length;i) {for(int j0;ji;j) {if(nums[i]nums[j]) {dp[i]Math.max(dp[i], dp[j]1);}}}//从dp数组中再找到一个最大值int result 0;for(int i0;inums.length;i) {resultMath.max(result,dp[i] );}return result;}674.最长连续递增序列 思路 每一个元素和上一个元素比较如果满足条件就1.如果不满足就初始化为1.
public int findLengthOfLCIS(int[] nums) {//定义dp数组dp[i]代表以i为结尾的最长连续递增子序列int dp[]new int[nums.length];//初始化dp[0]1;//遍历顺序从左到右for(int i1;inums.length;i) {if(nums[i]nums[i-1]) {dp[i]dp[i-1]1;}else {dp[i]1;}}int result 0;for(int i0;idp.length;i) {resultMath.max(result, dp[i]);}return result;}718.最长重复子数组 思路 定义dp数组含义 dp[i][j]代表数组1到i-1数组2到j-1的最长重复子数组。 遍历顺序先遍历数组1然后遍历数组2如果nums1[i-1]nums[j-1]。更新dp数组。 结果返回dp数组的最大值即可。 public int findLength(int[] nums1, int[] nums2) {//dp数组定义代表dp[i][j]代表数组1到i-1数组2到i-2的最长重复子数组int dp[][]new int[nums1.length1][nums2.length1];//初始化int result0;//记录最大的结果for(int i1;inums1.length1;i) {for(int j1;jnums2.length1;j) {if(nums1[i-1]nums2[j-1]) {dp[i][j]dp[i-1][j-1]1;}resultMath.max(result, dp[i][j]);}}return result;}1143.最长公共子序列 思路 这道题和前一道的区别是这道题不要求连续了。所以要考虑字符串不相等的情况不相等的时候可以从上边或者左边推出来。 public int longestCommonSubsequence(String text1, String text2) {int dp[][]new int[text1.length()1][text2.length()1];//确定dp数组含义//dp[i][j]表示字符串1[0,i-1]字符串2[0,j-1]的最长重复子数组因为这里不考虑需要字符连续的情况。所以需要考虑不相同的qingk for(int i1;itext1.length();i) {for(int j1;jtext2.length();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[text1.length()][text2.length()];}1035.不相交的线 思路 其实就是在求两个数字数组的最长公共子序列。 public int maxUncrossedLines(int[] nums1, int[] nums2) {int dp[][]new int[nums1.length1][nums2.length1];for(int i1;inums1.length;i) {for(int j1;jnums2.length;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[nums1.length][nums2.length];}53.最大子数组和 思路 dp[i]是以i结尾的最大数组和。当前这个值由dp[i-1]nums[i],nums[i]中两个数之间选一个最大的。 public int maxSubArray(int[] nums) {int dp[]new int[nums.length];//dp数组含义,以i为结尾的最大子数组和if(nums.length1) {return nums[0];}int resultInteger.MIN_VALUE;//初始化dp[0]nums[0];for(int i1;inums.length;i) {dp[i]Math.max(nums[i], dp[i-1]nums[i]);resultMath.max(result, dp[i]);}return result;}392.判断子序列 思路 这道题就是求最长公共子序列求出最长公共子序列的长度然后再和最短的子串长度进行笔记然后判断这两个是不是相等即可。 public boolean isSubsequence(String s, String t) {int dp[][]new int[s.length()1][t.length()1];//确定dp数组的含义dp[i][j]表示字符串1以i-1为结尾字符串2以j-1为结尾的最长子序列长度for(int i1;is.length();i) {for(int j1;jt.length();j) {if(s.charAt(i-1)t.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[s.length()][t.length()]s.length();}115.不同的子序列 思路 记住dp定义。 然后dp可以有两个状态推过来然后记住下一次操作。当s[i-1]和t[j-1]相等时可以选择用它还可以选择不用它。 public int numDistinct(String s, String t) {int dp[][]new int[s.length()1][t.length()1];//确定dp数组的含义,dp[i][j]表示以i-1结尾的字符串中有多少个以j-1结尾的子串//初始化dp[0][0]1;dp[0][1]0;dp[1][0]1;for (int i 0; i s.length() 1; i) {dp[i][0] 1;}for(int i1;is.length();i) {for(int j1;jt.length();j) {if(s.charAt(i-1)t.charAt(j-1)) {//这里分为用i-1的情况和不用i-1的情况例如bagg,bag.dp[i][j]dp[i-1][j-1]dp[i-1][j];}else {dp[i][j]dp[i-1][j];//不相等的话就往前推一位}}}return dp[s.length()][t.length()];}583.两个字符串的删除操作 思路 如果相同dp数组就按照dp[i-1][j-1] 如果比较的字符串不同那么dp数组就在删上一个、删下一个、两个都删里边选一个比较小的。
public int minDistance(String word1, String word2) {int dp[][]new int[word1.length()1][word2.length()1];//dp数组含义,dp[i][j]以i-1结尾的word1和j-1结尾的word2要达到相同的长度需要删除几个元素//初始化for(int i0;iword1.length();i) {dp[i][0]i;}for(int j0;jword2.length();j) {dp[0][j]j;}for(int i1;iword1.length();i) {for(int j1;jword2.length();j) {if(word1.charAt(i-1)word2.charAt(j-1)) {//如果当前两个字母相等的话,删不删都无所谓了dp[i][j]dp[i-1][j-1];}else {//否则就要取删i-1删j-1还是都删中最小的一个dp[i][j]Math.min(dp[i-1][j]1, Math.min(dp[i][j-1]1, dp[i-1][j-1]2));}}}return dp[word1.length()][word2.length()];}72.编辑距离 思路 dp[][]数组定义 dp数组初始化 根据上一个的状态推出dp[i][j]。要不就删一个要不就更改一个。
public int minDistance(String word1, String word2) {int dp[][]new int[word1.length()1][word2.length()1];//dp数组含义,dp[i][j]表示以i-1结尾的word1要变成j-1为结尾的word2最少操作的次数//初始化for(int i0;iword1.length();i) {dp[i][0]i;}for(int j0;jword2.length();j) {dp[0][j]j;}for(int i1;iword1.length();i) {for(int j1;jword2.length();j) {if(word1.charAt(i-1)word2.charAt(j-1)) {//如果当前两个字母相等的话,最小移动次数就是去掉这两个字母的移动次数dp[i][j]dp[i-1][j-1];}else {//否则就要取删i-1删j-1还是更改一个的最小次数dp[i][j]Math.min(dp[i-1][j]1, Math.min(dp[i][j-1]1, dp[i-1][j-1]1));}}}return dp[word1.length()][word2.length()];}647.回文子串 思路 定义dp数组的含义。 然后当s[i]s[j]时分析三种情况。 如果满足回文串的时候返回三种数量即可。 public int countSubstrings(String s) {boolean dp[][]new boolean[s.length()][s.length()];//dp[i][j]含义表示以i为开头以j为结尾的子串是不是回文串int result0;//初始化都初始为false‘//遍历顺序从左下角到右上角开始遍历for(int is.length()-1;i0;i--) {for(int ji;js.length();j) {if(s.charAt(i)s.charAt(j)) {//如果两个字母相等if(j-i1) {//一定是回文串可能是一个字符串也可能是两个相同的字符串result;dp[i][j]true;}else if(dp[i1][j-1]) {//如果相差距离大于1里面的子串是回文串那么这个也就是回文串了result;dp[i][j]true;}}}}return result;}516.最长回文子序列 思路 定义dp数组含义然后dp数组可以从i1和j-1推出。 或者只考虑一端的数子然后取这两个较大的值。 最后取一个较大的结果即可。 public int longestPalindromeSubseq(String s) {int dp[][]new int[s.length()1][s.length()1];//dp数组含义表示dp[i][j]从i开始到j结束的最长的回文子序列//初始化for(int i0;is.length();i) {dp[i][i]1;}//遍历顺序从左下角到右上角遍历for(int is.length()-1;i0;i--) {for(int ji1;js.length();j) {if(s.charAt(i)s.charAt(j)) {//如果两个字母相等的话那么这个字符串也是一个回文字符串dp[i][j]dp[i1][j-1]2;}else {//如果不是取两个之间较大的一个dp[i][j]Math.max(dp[i1][j], dp[i][j-1]);}}}return dp[0][s.length()-1];}
