/**
* @param {number} m
* @param {number} n
* @return {number}
*/
var uniquePaths = function(m, n) {
let dp = new Array(m)
dp[0] = new Array(n)
dp[0].fill(1)
for(let i = 1; i < m; i++){
dp[i] = new Array(n)
for(let j = 0; j < n; j++){
if(j === 0) dp[i][0] = 1
else dp[i][j] = dp[i-1][j] + dp[i][j-1]
}
}
return dp[m-1][n-1]
};
/**
* @param {number[][]} obstacleGrid
* @return {number}
*/
var uniquePathsWithObstacles = function(obstacleGrid) {
let m = obstacleGrid.length
let n = obstacleGrid[0].length
let dp = new Array(m)
// 初始化数组
for(let i = 0; i < m; i++){
dp[i] = new Array(n)
if(i === 0) dp[0][0] = !obstacleGrid[0][0]
else{
if(obstacleGrid[i][0] === 1) dp[i][0] = 0
else dp[i][0] = dp[i-1][0]
}
}
for(let i = 1; i < n; i++){
if(obstacleGrid[0][i] === 1){
dp[0][i] = 0
}else{
dp[0][i] = dp[0][i-1]
}
}
console.log(dp)
for(let i = 1; i < m; i++){
for(let j = 1; j < n; j++){
if(obstacleGrid[i][j] === 1){
dp[i][j] = 0
}else{
dp[i][j] = dp[i-1][j] + dp[i][j-1]
}
}
}
return dp[m-1][n-1]
};
/**
* @param {number} n
* @return {number}
*/
var numTrees = function(n) {
let dp = new Array(n+1)
dp[0] = 1
dp[1] = 1
for(let i = 2; i <= n; i++){
dp[i] = 0
for(let j = 0; j <= i - 1; j++){
dp[i] += dp[j]*dp[i-j-1]
}
}
return dp[n]
};
/**
* @param {number} n
* @return {number}
*/
var integerBreak = function(n) {
let dp = new Array(n)
dp[2] = 1
for(let i = 3 ; i <= n; i++){
dp[i] = Math.max(1*(i-1), 1*dp[i-1])
for(let j = 2; j <= i -2; j++){
dp[i] = Math.max(dp[i], Math.max(j*(i-j), j*dp[i-j]))
}
// console.log(`dp[${i}]=${dp[i]}`)
}
return dp[n]
};
/**
* @param {number[]} nums
* @return {boolean}
*/
var canPartition = function(nums) {
let sum = 0
for(let i = 0; i < nums.length; i++){
sum += nums[i]
}
if(sum%2 !== 0) return false
let n = sum/2
let dp = new Array(n+1).fill(0)
dp[0] = 0
for(let i = 0; i < nums.length; i++){
for(let j = n; j >= nums[i]; j--){
dp[j] = Math.max(dp[j], dp[j - nums[i]] + nums[i])
}
// console.log(dp)
}
if(dp[n] === n) return true
return false
};
/**
* @param {number[]} stones
* @return {number}
*/
var lastStoneWeightII = function(stones) {
let sum = 0
for(let i = 0; i < stones.length; i++){
sum += stones[i]
}
let a = Math.floor(sum/2)
let dp = new Array(a+1).fill(0)
for(let i = 0; i < stones.length; i++){
for(let j = a; j >= stones[i]; j--){
dp[j] = Math.max(dp[j], dp[j - stones[i]] + stones[i])
}
}
return (sum - dp[a]) - dp[a]
};
/**
* @param {number[]} nums
* @param {number} target
* @return {number}
*/
var findTargetSumWays = function(nums, target) {
let sum = 0
for(let i = 0; i < nums.length; i++){
sum += nums[i]
}
if((sum + target) % 2 !== 0 ) return false
if( sum < target) return false
let left = (sum + target) / 2
if(left < 0) return false
let dp = new Array(left + 1).fill(0)
dp[0] = 1
for(let i = 0; i < nums.length; i++){
for(let j = left; j >= nums[i]; j--){
dp[j] += dp[j - nums[i]]
}
}
return dp[left]
};
/**
* @param {string[]} strs
* @param {number} m
* @param {number} n
* @return {number}
*/
var findMaxForm = function(strs, m, n) {
// 统计每个str的0,1个数
let zeroArr = new Array(strs.length).fill(0)
let oneArr = new Array(strs.length).fill(0)
for(let i = 0; i < strs.length; i++){
let str = strs[i].split('')
str.forEach((char) => {
if(char == 0) zeroArr[i] ++
else if(char == 1) oneArr[i] ++
})
}
// console.log(zeroArr,oneArr)
// 初始化dp数组
let dp = new Array()
for(let i = 0; i <= m; i++){
dp.push(new Array(n+1).fill(0))
}
for(let k = 0; k < strs.length; k++){
for(let i = m; i >= zeroArr[k]; i--){
for(let j = n; j >= oneArr[k]; j--){
// 更新dp
dp[i][j] = Math.max(dp[i][j], dp[i-zeroArr[k]][j-oneArr[k]]+1)
// console.log(i,j,dp)
}
}
}
return dp[m][n]
};
/**
* @param {number} amount
* @param {number[]} coins
* @return {number}
*/
var change = function(amount, coins) {
let dp = new Array(amount + 1).fill(0)
dp[0] = 1
for(let i = 0; i < coins.length; i++){
for(let j = coins[i]; j <= amount; j++){
dp[j] += dp[j - coins[i]]
}
// console.log(dp)
}
return dp[amount]
};
/**
* @param {number[]} nums
* @param {number} target
* @return {number}
*/
var combinationSum4 = function(nums, target) {
let dp = new Array(target + 1).fill(0)
dp[0] = 1
for(let i = 1; i <= target; i++){
for(let j = 0; j < nums.length; j++){
if(i >= nums[j]){
dp[i] += dp[i - nums[j]]
}
}
}
return dp[target]
};
/**
* @param {number} n
* @return {number}
*/
var climbStairs = function(n) {
let dp = new Array(n+1).fill(0)
dp[0] = 1
for(let j = 1; j <= n ;j++){
for(let i = 1; i <= 2; i++){
if(j >= i){
dp[j] += dp[j - i]
}
}
}
return dp[n]
};
/**
* @param {number[]} coins
* @param {number} amount
* @return {number}
*/
var coinChange = function(coins, amount) {
let dp = new Array(amount + 1).fill(Infinity)
dp[0] = 0
for(let i = 0; i < coins.length; i++){
for(let j = coins[i]; j <= amount; j++){
dp[j] = Math.min(dp[j], dp[j - coins[i]] + 1)
}
}
// console.log(dp)
return dp[amount] === Infinity ? -1 : dp[amount]
};
/**
* @param {number} n
* @return {number}
*/
var numSquares = function(n) {
let dp = new Array(n + 1).fill(Infinity)
dp[0] = 0
let num = Math.sqrt(n)
if(num % 1 === 0) return 1
num = Math.floor(num)
for(let i = 1; i <= num; i++){
for(let j = i*i; j <= n; j++){
dp[j] = Math.min(dp[j], dp[j - i*i] + 1)
}
}
return dp[n]
};
/**
* @param {string} s
* @param {string[]} wordDict
* @return {boolean}
*/
var wordBreak = function(s, wordDict) {
let n = s.length
let dp = new Array( n + 1).fill(false)
dp[0] = true
let set = new Set(wordDict)
for(let i = 0; i <= n; i++){
for(let j = 0; j < i; j++){
let str = s.substr(j, i - j)
if(set.has(str) && dp[j]){
dp[i] = true
}
}
}
console.log(dp)
return dp[n]
};
/**
* @param {number[]} nums
* @return {number}
*/
var rob = function(nums) {
if(nums.length === 1) return nums[0]
let dp = new Array(nums.length)
dp[0] = nums[0]
dp[1] = Math.max(nums[0], nums[1])
for(let i = 2; i < nums.length; i++){
dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i])
}
return dp[nums.length - 1]
};
/**
* @param {number[]} nums
* @return {number}
*/
var rob = function(nums) {
if(nums.length === 1) return nums[0]
function fn(start, end){
// 如果考虑的情况只有一个 直接返回这个金额
if(start === end) return nums[end]
let dp = new Array(nums.length - 1)
dp[0] = nums[start]
dp[1] = Math.max(nums[start], nums[start+1])
for(let i = 2; i <= dp.length - 1; i++){
dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i + start])
}
console.log('dp:',dp)
return dp[dp.length - 1]
}
return Math.max(fn(0, nums.length - 2), fn(1, nums.length - 1))
};
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @return {number}
*/
var rob = function(root) {
function backtracking(node){
if(node === null) return [0, 0]
// 拿到左右子树的返回结果
let left = backtracking(node.left)
let right = backtracking(node.right)
// 不拿当前节点 左右节点都可以考虑（选择拿或者不拿其中较大者）
let val1 = Math.max(left[0], left[1]) + Math.max(right[0], right[1])
// 拿当前节点 左右节点则不能考虑
let val2 = node.val + left[0] + right[0]
return [val1,val2]
}
let dp = backtracking(root)
return Math.max(dp[0], dp[1])
};
贪心
/**
* @param {number[]} prices
* @return {number}
*/
var maxProfit = function(prices) {
let min = prices[0]
let max = 0
for(let i = 1; i < prices.length; i++){
max = Math.max(max, prices[i] - min)
min = Math.min(min, prices[i])
}
return max
};
动态规划
/**
* @param {number[]} prices
* @return {number}
*/
var maxProfit = function(prices) {
let dp = new Array(prices.length)
for(let i = 0; i < prices.length; i++){
dp[i] = [0,0]
}
dp[0][0] = -prices[0]
dp[0][1] = 0
for(let i = 1; i < prices.length; i++){
dp[i][0] = Math.max(dp[i-1][0], -prices[i])
dp[i][1] = Math.max(dp[i-1][1], dp[i-1][0] + prices[i])
}
return dp[dp.length - 1][1]
};
贪心
/**
* @param {number[]} prices
* @return {number}
*/
var maxProfit = function(prices) {
if(prices.length <= 1) return 0
let count = 0
for(let i = 1; i < prices.length; i++){
if(prices[i] - prices[i-1] > 0)
count += prices[i] - prices[i-1]
}
return count
};
动态规划
/**
* @param {number[]} prices
* @return {number}
*/
var maxProfit = function(prices) {
let dp = new Array(prices.length)
for(let i = 0; i < prices.length; i++){
dp[i] = [0,0]
}
dp[0][0] = -prices[0] // 持有股票所得金额
dp[0][1] = 0 // 不持有股票所得金额
for(let i = 1; i < prices.length; i++){
dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1] - prices[i])
dp[i][1] = Math.max(dp[i-1][1], dp[i-1][0] + prices[i])
}
return dp[dp.length - 1][1]
};
/**
* @param {number[]} prices
* @return {number}
*/
var maxProfit = function(prices) {
let dp = new Array(prices.length)
for(let i = 0; i < prices.length; i++){
dp[i] = [0,0,0,0,0]
}
dp[0][1] = dp[0][3] = -prices[0]
for(let i = 1; i < prices.length; i++){
dp[i][0] = dp[i-1][0]
dp[i][1] = Math.max(dp[i-1][1], dp[i-1][0] - prices[i])
dp[i][2] = Math.max(dp[i-1][2], dp[i-1][1] + prices[i])
dp[i][3] = Math.max(dp[i-1][3], dp[i-1][2] - prices[i])
dp[i][4] = Math.max(dp[i-1][4], dp[i-1][3] + prices[i])
}
return dp[dp.length - 1][4]
};
/**
* @param {number} k
* @param {number[]} prices
* @return {number}
*/
var maxProfit = function(k, prices) {
if(k === 0) return 0
if(prices.length === 0) return 0
let dp = new Array(prices.length)
for(let i = 0; i < prices.length; i++){
dp[i] = new Array(2*k+1)
}
dp[0][0] = 0
for(let j = 1; j < 2*k + 1; j++){
if(j % 2 === 0){
dp[0][j] = 0
}else dp[0][j] = -prices[0]
}
for(let i = 1; i < prices.length; i++){
for(let j = 0; j < 2*k - 1; j += 2){
if(j === 0) dp[i][0] = dp[i-1][0]
// 买入
dp[i][j+1] = Math.max(dp[i-1][j+1], dp[i-1][j] - prices[i])
// 卖出
dp[i][j+2] = Math.max(dp[i-1][j+2], dp[i-1][j+1] + prices[i])
}
}
return dp[prices.length-1][2*k]
};
/**
* @param {number[]} prices
* @return {number}
*/
var maxProfit = function(prices) {
if(prices.length === 1) return 0
let dp = new Array(prices.length)
for(let i = 0; i < prices.length; i++){
dp[i] = [0,0,0,0]
}
dp[0][0] = -prices[0]
for(let i = 1; i < prices.length; i++){
// 买入股票状态 1.保持之前的买入状态 2.前一天冷冻/前一天过了冷冻 今天买入
dp[i][0] = Math.max(dp[i-1][0],dp[i-1][1]-prices[i],dp[i-1][3]-prices[i])
// 卖出股票并且过了冷冻期状态 前一天是冷冻期/保持前一天的卖出状态
dp[i][1] = Math.max(dp[i-1][1], dp[i-1][3])
// 今天卖出股票 前一天是买入状态
dp[i][2] = dp[i-1][0] + prices[i]
// 今天是冷冻期 前一天卖出股票
dp[i][3] = dp[i-1][2]
}
// 返回卖出状态 今日卖出 今日冷冻期 三者的最大金额
return Math.max(dp[dp.length-1][1],dp[dp.length-1][2],dp[dp.length-1][3])
};
贪心
/**
* @param {number[]} prices
* @param {number} fee
* @return {number}
*/
var maxProfit = function(prices, fee) {
let result = 0
let min = prices[0]
for(let i = 1; i < prices.length; i++){
// 1. 更新最低价格 相当于前一次已经将股票卖出 现在确定最低的买入价格
if(prices[i] < min){
min = prices[i]
}
// 2. 此时如果未拥有股票买入不划算 如果拥有股票卖出会亏本 保持现状
if(prices[i] >= min && prices[i] <= min + fee){
continue
}
// 3. 计算利润
if(prices[i] > min + fee){
result += prices[i] - min - fee
min = prices[i] - fee
}
}
return result
};
动态规划
/**
* @param {number[]} prices
* @param {number} fee
* @return {number}
*/
var maxProfit = function(prices, fee) {
if(prices.length === 1) return 0
let dp = new Array(prices.length)
for(let i = 0; i < prices.length; i++){
dp[i] = [0, 0]
}
dp[0][0] = -prices[0]
for(let i = 1; i < prices.length; i++){
dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1] - prices[i])
dp[i][1] = Math.max(dp[i-1][1], dp[i-1][0] + prices[i] - fee)
}
return dp[dp.length-1][1]
};
/**
* @param {number[]} nums
* @return {number}
*/
var lengthOfLIS = function(nums) {
let dp = new Array(nums.length).fill(1)
let result = 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)
}
result = Math.max(result,dp[i])
}
// console.log(dp)
return result
};
/**
* @param {number[]} nums
* @return {number}
*/
var findLengthOfLCIS = function(nums) {
let dp = new Array(nums.length).fill(1)
let result = 1
for(let i = 1; i < nums.length; i++){
if(nums[i] > nums[i-1]){
dp[i] = dp[i-1] + 1
}
result = Math.max(result, dp[i])
}
return result
};
/**
* @param {number[]} nums1
* @param {number[]} nums2
* @return {number}
*/
var findLength = function(nums1, nums2) {
let dp = new Array(nums1.length+1)
for(let i = 0; i <= nums1.length; i++){
dp[i] = new Array(nums2.length + 1).fill(0)
}
let ans = 0
for(let i = 1; i <= nums1.length; i++){
for(let j = 1; j <= nums2.length; j++){
if(nums1[i-1] == nums2[j-1]){
dp[i][j] = dp[i-1][j-1] + 1
}
ans = Math.max(ans, dp[i][j])
}
}
return ans
};
/**
* @param {string} text1
* @param {string} text2
* @return {number}
*/
var longestCommonSubsequence = function(text1, text2) {
let dp = new Array(text1.length + 1)
for(let i = 0; i <= text1.length; i++){
dp[i] = new Array(text2.length + 1).fill(0)
}
let ans = 0
for(let i = 1; i <= text1.length; i++){
for(let j = 1; j <= text2.length; j++){
if(text1[i-1] === text2[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])
}
ans = Math.max(ans, dp[i][j])
}
}
return ans
};
/**
* @param {number[]} nums1
* @param {number[]} nums2
* @return {number}
*/
var maxUncrossedLines = function(nums1, nums2) {
let dp = new Array(nums1.length + 1)
for(let i = 0; i <= nums1.length; i++){
dp[i] = new Array(nums2.length+1).fill(0)
}
let ans = 0
for(let i = 1; i <= nums1.length; i++){
for(let j = 1; j <= nums2.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])
}
ans = Math.max(ans, dp[i][j])
}
}
return ans
};
贪心
/**
* @param {number[]} nums
* @return {number}
*/
var maxSubArray = function(nums) {
if(nums.length === 1) return nums[0]
let count = 0
let max = -10000
for(let i = 0; i < nums.length; i++){
count += nums[i]
max = Math.max(count, max)
// console.log('max, count',max, count)
if(count < 0){
count = 0
}
}
return max
};
动态规划
/**
* @param {number[]} nums
* @return {number}
*/
var maxSubArray = function(nums) {
let dp = new Array(nums.length)
dp[0] = nums[0]
let ans = nums[0]
for(let i = 1; i < nums.length; i++){
dp[i] = Math.max(dp[i-1] + nums[i], nums[i])
ans = Math.max(ans, dp[i])
}
return ans
};
/**
* @param {string} s
* @param {string} t
* @return {boolean}
*/
var isSubsequence = function(s, t) {
let dp = new Array(s.length+1)
for(let i = 0; i <= s.length; i++){
dp[i] = new Array(t.length+1).fill(0)
}
for(let i = 1; i <= s.length; i++){
for(let j = 1; j <= t.length; j++){
if(s[i-1] == t[j-1]){
dp[i][j] = dp[i-1][j-1] + 1
}else{
dp[i][j] = dp[i][j-1]
}
}
}
return dp[s.length][t.length] == s.length
};
/**
* @param {string} s
* @param {string} t
* @return {number}
*/
var numDistinct = function(s, t) {
let dp = new Array(s.length+1)
for(let i = 0; i <= s.length; i++){
dp[i] = new Array(t.length + 1).fill(0)
dp[i][0] = 1
}
for(let i = 1; i <= s.length; i++){
for(let j = 1; j <= t.length; j++){
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]
}
}
}
return dp[s.length][t.length]
};
/**
* @param {string} word1
* @param {string} word2
* @return {number}
*/
var minDistance = function(word1, word2) {
let dp = new Array(word1.length + 1)
for(let i = 0; i <= word1.length; i++){
dp[i] = new Array(word2.length+1)
dp[i][0] = i
}
for(let j = 0; j <= word2.length; j++){
dp[0][j] = j
}
for(let i = 1; i <= word1.length; i++){
for(let j = 1; j <= word2.length; 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, dp[i-1][j-1] + 2)
}
}
}
return dp[word1.length][word2.length]
};
/**
* @param {string} word1
* @param {string} word2
* @return {number}
*/
var minDistance = function(word1, word2) {
let dp = new Array(word1.length+1)
for(let i = 0; i <= word1.length; i++){
dp[i] = new Array(word2.length+1)
dp[i][0] = i
}
for(let j = 0; j <= word2.length; j++){
dp[0][j] = j
}
for(let i = 1; i <= word1.length; i++){
for(let j = 1; j <= word2.length; 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, dp[i-1][j-1] + 1)
}
}
}
return dp[word1.length][word2.length]
};
/**
* @param {string} s
* @return {number}
*/
var countSubstrings = function(s) {
let dp = new Array(s.length)
for(let i = 0; i < s.length; i++){
dp[i] = new Array(s.length).fill(false)
}
let ans = 0
for(let i = s.length - 1 ; i >= 0; i --){
for( let j = i; j < s.length; j ++){
if(s[i] == s[j]){
if( (j - i) <= 1){
dp[i][j] = true
}else{
dp[i][j] = dp[i+1][j-1]
}
}
if(dp[i][j]) ans ++
}
}
return ans
};
/**
* @param {string} s
* @return {number}
*/
var longestPalindromeSubseq = function(s) {
let dp = new Array(s.length)
for(let i = 0; i < s.length; i++){
dp[i] = new Array(s.length).fill(0)
dp[i][i] = 1
}
for(let i = s.length - 1; i >=0 ; i--){
for(let j = i+1; j < s.length; j++){
if(s[i] == s[j]){
dp[i][j] = dp[i+1][j-1] + 2
}else{
dp[i][j] = Math.max(dp[i][j-1], dp[i+1][j])
}
}
}
return dp[0][s.length-1]
};
