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)
思路 讲确定两个数组的问题转换化简为确定一个数组， 把整个数组可以被分成两个子数组，两个子数组中数字和分别为left和right，则有 left - right = target left + right = sum 可推导出：left - sum + left = target; left = (sum + target)/2 问题转换为组合和为left的问题，可以用回溯暴力破解。
var findMaxForm = function(strs, m, n) { let dp = Array.from(Array(m+1), () =>Array(n+1).fill(0)); for (let str of strs) { let zeroNum = 0, oneNum = 0; for (let s of str) { if (s === '1') oneNum++; else zeroNum++; } for(let i = m; i >= zeroNum; i--) { for (let j = n; j >= oneNum; j--) { dp[i][j] = Math.max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1); } } } return dp[m][n]; };
let readline = require('readline') const rl = readline.createInterface({ input:process.stdin, output:process.stdout99 }) let inputArr = [] rl.on('line',function(line){ inputArr.push(line.split(' ')) }).on('close',function(){ let n = parseInt(inputArr[0][0]) let m = parseInt(inputArr[0][1]) let w = inputArr[1].map(Number) let v = inputArr[2].map(Number) let num = inputArr[3].map(Number) let dp = Array(n+1).fill(0) //遍历物品 for (let i=0;i<m;i++){ //背包 for(let j = n;j>=w[i];j--){ for(let k=1;k<=num[i] && k*w[i]<=j;k++){ dp[j] = Math.max(dp[j],dp[j-w[i]*k]+v[i]*k) } } } console.log(dp[n]) })
var repeatedSubstringPattern = function (s) { let ss = s + s ss = ss.slice(1, ss.length) ss = ss.slice(0, ss.length - 1) if (ss.includes(s)) { returntrue } else { returnfalse } }
var partitionLabels = function(s) { let map = newMap() for(let i=0;i<s.length;i++){ map.set(s[i],i) } let result = [] let left=0,right=0 for(let i=0;i<s.length;i++){ right = Math.max(right,map.get(s[i])) // 找到分割点的标志。 if (right === i){ result.push(right-left+1) left = i+1 } } return result };
