96 单词拆分

• 动态规划
• 完全背包：背包-字符串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。

/*** @param {string} s* @param {string[]} wordDict* @return {boolean}*/
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;
};

97 最长递增子序列

• 动态规划
• 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。

/*** @param {number[]} nums* @return {number}*/
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;
};

98 乘积最大子数组

• 动态规划
• 由于在数组中有负数，因此这里设置两个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])。

/*** @param {number[]} nums* @return {number}*/
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;
};

99 分割等和子集

• 动态规划
• 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])。

/*** @param {number[]} nums* @return {boolean}*/
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;
};

100 最长有效括号

• 动态规划
• dp[i]：以s[i]为结尾的最长有效子串的长度。
• 初始化：dp[i] = 0。
• (1) 若s[i] = “(”：dp[i] = 0。
• (2) 若s[i] = “)”：
  ① s[i - 1] = “(”：例如…( )，s[i - 1]和s[i]为有效括号，因此dp[i] = dp[i - 2] + 2。
  ② s[i - 1] = “)”：例如…( (…) )，此时判断s[i - dp[i - 1] - 1]的括号方向，若为"("，则与s[i]为有效括号，因此dp[i] = dp[i - 1] + 2 + 以s[i - dp[i - 1] - 2]为结尾的有效字串的长度。
•        … )                       (                         (          …     )           )
• i - dp[i - 1] - 2      i - dp[i - 1] - 1      i - dp[i - 1]   …   i - 1         i

/*** @param {string} s* @return {number}*/
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;
};