文章目录 96 单词拆分 97 最长递增子序列 98 乘积最大子数组 99 分割等和子集 100 最长有效括号
动态规划 完全背包：背包-字符串s，物品-wordDict中的单词，可使用多次。 问题转换：s能否被wordDict中的单词组成。 dp[i]：长度为i的字符串s[0, i]能否被wordDict组成，dp[i] = true / false。 两层for循环遍历顺序：先背包后物品。 i为字符串长度，j从0开始，一直遍历到i - 1，若s[j, i]在wordDict中，且s[0, i - j]能被wordDict组成，则s[0, i]能被wordDict组成。 初始化：dp[0] = true，其他为false。 javascript">
var wordBreak = function ( s, wordDict ) { let dp = Array ( s. length + 1 ) . fill ( 0 ) ; dp[ 0 ] = 1 ; for ( let i = 1 ; i <= s. length; i++ ) { for ( let j = 0 ; j < i; j++ ) { if ( wordDict. includes ( s. slice ( j, i) ) && dp[ j] == 1 ) { dp[ i] = 1 ; } } } return dp[ s. length] ? true : false ;
} ;
动态规划 dp[i]：以nums[i]为结尾的最长递增子序列的长度。 第一层for循环遍历每个数字i，第二层for循环遍历从0到i - 1的每个数字j。 若nums[i] > nums[j]，则以nums[i]为结尾的最长递增子序列的长度 = max(以nums[j]为结尾的最长递增子序列的长度 + 1, dp[i])。 初始化：因为每个数字的最长递增子序列的长度最小为1，所以dp[i] = 1。 javascript">
var lengthOfLIS = function ( nums ) { let dp = Array ( nums. length) . fill ( 1 ) ; let res = 1 ; for ( let i = 1 ; i < nums. length; i++ ) { for ( let j = 0 ; j < i; j++ ) { if ( nums[ i] > nums[ j] ) { dp[ i] = Math. max ( dp[ i] , dp[ j] + 1 ) ; } } res = Math. max ( res, dp[ i] ) ; } return res;
} ;
动态规划 由于在数组中有负数，因此这里设置两个dp数组。 dp_max[i]：以nums[i]为结尾的子数组的最大乘积，dp_min[i]：以nums[i]为结尾的子数组的最小乘积。 dp_max[i] = max(nums[i] * 以nums[i - 1]为结尾的子数组的最大乘积, nums[i] * 以nums[i - 1]为结尾的子数组的最小乘积, nums[i])。 dp_min[i] = min(nums[i] * 以nums[i - 1]为结尾的子数组的最大乘积, nums[i] * 以nums[i - 1]为结尾的子数组的最小乘积, nums[i])。 javascript">
var maxProduct = function ( nums ) { let dp_max = Array ( nums. length) . fill ( 0 ) ; let dp_min = Array ( nums. length) . fill ( 0 ) ; let res = nums[ 0 ] ; dp_max[ 0 ] = nums[ 0 ] , dp_min[ 0 ] = nums[ 0 ] ; for ( let i = 1 ; i < nums. length; i++ ) { dp_max[ i] = Math. max ( Math. max ( nums[ i] * dp_max[ i - 1 ] , nums[ i] * dp_min[ i - 1 ] ) , nums[ i] ) ; dp_min[ i] = Math. min ( Math. min ( nums[ i] * dp_max[ i - 1 ] , nums[ i] * dp_min[ i - 1 ] ) , nums[ i] ) ; res = Math. max ( res, dp_max[ i] ) ; } return res;
} ;
动态规划 0 / 1背包 dp[j]：容量为j的背包最大价值为dp[j]。 target为nums的总和，若使用nums中的物品(数字 = 价值)能把容量为target / 2的背包装满，价值为target / 2，则能够分割等和子集。 根据题意，若target为奇数，则不能够分割等和子集。 第一层for循环遍历物品，第二层for循环遍历背包容量。 dp[j] = max(dp[j], dp[j - nums[i]] + nums[i])。 javascript">
var canPartition = function ( nums ) { let target = nums. reduce ( ( sums, item ) => sums + item, 0 ) ; if ( target % 2 == 1 ) { return false ; } else { target = Math. floor ( target / 2 ) ; } let dp = Array ( target + 1 ) . fill ( 0 ) ; for ( let i = 0 ; i < nums. length; i++ ) { for ( let j = target; j >= nums[ i] ; j-- ) { dp[ j] = Math. max ( dp[ j] , dp[ j - nums[ i] ] + nums[ i] ) ; } } return dp[ target] == target? true : false ;
} ;
动态规划 dp[i]：以s[i]为结尾的最长有效子串的长度。 初始化：dp[i] = 0。 (1) 若s[i] = “(”：dp[i] = 0。 (2) 若s[i] = “)”： … ) ( ( … ) ) i - dp[i - 1] - 2 i - dp[i - 1] - 1 i - dp[i - 1] … i - 1 i javascript">
var longestValidParentheses = function ( s ) { let dp = Array ( s. length) . fill ( 0 ) ; let res = 0 ; for ( let i = 1 ; i < s. length; i++ ) { if ( s[ i] == "(" ) { dp[ i] = 0 ; } else if ( s[ i] == ")" ) { if ( s[ i - 1 ] == "(" ) { if ( i - 2 >= 0 ) { dp[ i] = dp[ i - 2 ] + 2 ; } else { dp[ i] = 2 ; } } else if ( s[ i - 1 ] == ")" && s[ i - dp[ i - 1 ] - 1 ] == "(" ) { if ( i - dp[ i - 1 ] - 2 >= 0 ) { dp[ i] = dp[ i - 1 ] + dp[ i - dp[ i - 1 ] - 2 ] + 2 ; } else { dp[ i] = dp[ i - 1 ] + 2 ; } } } res = Math. max ( res, dp[ i] ) ; } return res;
} ;
