中序 var inorderTraversal = function (root) { // 入栈:左->右 // 出栈:左 中 右 let res = [] if (!root) return res const stack = [] cur = root while (cur || stack.length){ if (cur){ stack.push(cur) cur = cur.left } else{ cur = stack.pop() res.push(cur.val) cur = cur.right } } return res }
超时了，129/132 var countSubstrings = function(s) { let num = 0 functionisHuiwen(t) { let p = 0;q = t.length-1 while (p<q){ if (t[p] != t[q]){ returnfalse } p++; q-- } returntrue } for (let i=0;i<s.length;i++){ for (let j=i+1;j<=s.length;j++){ console.log(isHuiwen(s.substring(i, j))) if (isHuiwen(s.substring(i,j))) num ++ } } return num };
动态规划 var countSubstrings = function(s) { let num = 0 let n = s.length let dp = Array.from({length:n},()=>Array(n).fill(false)) for(let i=n-1;i>=0;i--){ //j是尾巴，尾巴j大于等于头i for(let j=i;j<n;j++){ if (s[i]==s[j]){ if (j-i>1) { dp[i][j] = dp[i+1][j-1] } else dp[i][j] = true } if (dp[i][j] === true) num++ } } console.log(dp) return num };
if (s[i-1]==t[j-1]) dp[i][j] = dp[i-1][j-1] +dp[i-1][j],使用s[i-1]这个元素+不使用s[i-1]这个元素
else dp[i][j] = dp[i-1][j],模拟删除当前元素，也就是不考录当前的元素。
3、初始化：
dp[i][0] = 1(); t是空字符串的话，把s中元素全部删除可以得到t
dp[0][j] = 0; s为空字符串，t不可能出现在s中，所以未0
dp[0][0]= 1; s和t都为空字符串的话，只有一种可能
4、遍历顺序：
1 2 3 4 5 6 7 8 9 10 11 12 13 14
var numDistinct = function(s, t) { let n = s.length let m = t.length let dp = Array.from({length:n+1},()=>Array(m+1).fill(0)) for (let i=0;i<=n;i++) {dp[i][0]=1} for (let i=1;i<=n;i++){ for (let j=1;j<=m;j++){ //相等，可以选择使用s[i-1]或者不使用s[i-1] if (s[i-1]==t[j-1]) dp[i][j] = dp[i-1][j-1] + dp[i-1][j] else dp[i][j] = dp[i-1][j] //不相等说明s[i-1]用不了得删掉。 } } return dp[n][m] };
var minDistance = function(word1, word2) { let n = word1.length let m = word2.length let dp = Array.from({length:n+1},()=>Array(m+1).fill(0)) //这两个for循环用于初始化dp数组 for (let i=0;i<=n;i++){ dp[i][0] = i } for (let j=0;j<=m;j++){ dp[0][j] = j } for (let i=1;i<=n;i++){ for(let j=1;j<=m;j++){ if (word1[i-1] == word2[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] };
var minDistance = function(word1, word2) { let n= word1.length let m = word2.length let dp = Array.from({length:n+1},()=>Array(m+1).fill(0)) for (let i=0;i<=n;i++){ dp[i][0] = i } for (let j=0;j<=m;j++){ dp[0][j] = j } for (let i=1;i<=n;i++){ for (let j=1;j<=m;j++){ if (word1[i-1]==word2[j-1]) dp[i][j] = dp[i-1][j-1] else dp[i][j] = Math.min(dp[i][j-1]+1,dp[i-1][j]+1,dp[i-1][j-1]+1) } } return dp[n][m] };
if (nums[i]>nums[j]) dp[i] = max(dp[i],dp[j]+1)这里的含义是，取dp[j]+1的最大值。
3、初始化，子序列的长度最短为1
4、遍历顺序，外层遍历i(1 ~ n)，内层遍历j(0 ~ i-1)
还要注意并不是dp[n-1]才是最终的值，最大值应该是dp数组中的最大值。
1 2 3 4 5 6 7 8 9 10 11 12
var lengthOfLIS = function(nums) { let n = nums.length let dp = Array(n).fill(1) let result = 1 for(let i=1;i<n;i++){ for(let j=0;j<i;j++){ if (nums[i]>nums[j]) dp[i] = Math.max(dp[i],dp[j]+1) } if (dp[i]>result) result = dp[i] } return result };
var findLengthOfLCIS = function(nums) { let n = nums.length let dp = Array(n).fill(1) let result =1 for(let i=1;i<n;i++){ if(nums[i]>nums[i-1]) dp[i] = dp[i-1]+1 if (dp[i]>result) result = dp[i] } return result };
var findLength = function(nums1, nums2) { let n = nums1.length let m = nums2.length let dp = Array.from({length:n+1},()=>Array(m+1).fill(0)) let result = 0 for (let i=1;i<=n;i++){ for(let j=1;j<=m;j++){ if(nums1[i-1] == nums2[j-1]) dp[i][j]=dp[i-1][j-1]+1 if (dp[i][j] > result) result = dp[i][j] } } return result };
var maxUncrossedLines = function(nums1, nums2) { let n = nums1.length let m = nums2.length let dp = Array.from({length:n+1},()=>Array(m+1).fill(0)) for(let i = 1;i<=n;i++){ for(let 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] };
var maxProfit = function(prices) { let n = prices.length let dp = Array(4).fill(0) dp[0] = -prices[0] for(let i=0;i<n;i++){ let val0 = Math.max(dp[0],dp[3]-prices[i],dp[1]-prices[i]) let val1 = Math.max(dp[1],dp[3]) let val2 = dp[0]+prices[i] let val3 = dp[2] dp = [val0,val1,val2,val3] } returnMath.max(dp[1],dp[2],dp[3]) };
var rob = function(nums) { let n = nums.length let dp = Array(n+1).fill(0) dp[0] = nums[0] dp[1] = Math.max(dp[0],nums[1]) for (let i=2;i<n;i++){ dp[i] = Math.max(dp[i-2]+nums[i],dp[i-1]) } return dp[n-1] };
//ACM模式 let readline = require('readline') const rl = readline.createInterface({ input:process.stdin, output:process.stdout }); let inputArr = [] rl.on('line',function(line){ inputArr.push(line.split(' ')) }).on('close',function(){ let n = parseInt(inputArr[0][0]) let v = parseInt(inputArr[0][1]) let weight = [] let value = [] for (let i = 1;i<=n;i++){ weight.push(parseInt(inputArr[i][0])) value.push(parseInt(inputArr[i][1])) } let dp = Array(v+1).fill(0) for (let i=0;i<=n;i++){ //这边这个循环要注意，总写错j的起始值 for(let j=weight[i];j<=v;j++){ dp[j] = Math.max(dp[j],dp[j-weight[i]]+value[i]) } } console.log(dp[v]) })
var combinationSum4 = function(nums, target) { let n = target let m = nums.length let dp = Array(n+1).fill(0) dp[0] = 1 // 背包 for (let i=0;i<=n;i++){ // 物品 for (let j=0;j<m;j++){ if (i-nums[j] >=0) dp[i] += dp[i - nums[j]] } } return dp[n] };
rl.on('line',function(line){ var tokens = line.split(' ') let n = parseInt(tokens[0]) let m = parseInt(tokens[1]) let dp = Array(n+1).fill(0) dp[0] = 1 for (let i=0;i<=n;i++){ for (let j=1;j<=m && i-j>=0;j++){ dp[i] += dp[i-j] } } console.log(dp[n]) })
var coinChange = function(coins, amount) { let n = amount let m = coins.length let dp = Array(n+1).fill(Number.MAX_SAFE_INTEGER) dp[0] = 0 for(let i=0;i<m;i++){ console.log(dp) for(let j=coins[i];j<=n;j++){ dp[j] = Math.min(dp[j],dp[j-coins[i]]+1)
