/* * @lc app=leetcode.cn id=122 lang=javascript * * [122] 买卖股票的最佳时机 II */// @lc code=start /** * @param {number[]} prices * @return {number} */ var maxProfit = function(prices) { let profit_in = -prices[0], profit_out = 0, n = prices.length; for(let i =0; i < n; i++) { profit_out = Math.max(profit_out, profit_in + prices[i]); profit_in = Math.max(profit_in,profit_out - prices[i]); }return profit_out; };

/* * @lc app=leetcode.cn id=123 lang=javascript * * [123] 买卖股票的最佳时机 III */// @lc code=start /** * @param {number[]} prices * @return {number} */ var maxProfit = function(prices) { //第一次 买入， 卖出的利润 let profit_1_in = -prices[0], profit_1_out = 0; //继第一次之后，第二次买入卖出的利润 let profit_2_in = -prices[0], profit_2_out = 0; let n = prices.length; for (let i = 1; i < n; i++){ profit_2_out = Math.max(profit_2_out, profit_2_in + prices[i]); //第二次买入后的利润， 第一次卖出的利润 - prices[i] profit_2_in = Math.max(profit_2_in, profit_1_out - prices[i]); profit_1_out = Math.max(profit_1_out, profit_1_in + prices[i]); //第一次买入后，利润为 -prices[i] profit_1_in = Math.max(profit_1_in, -prices[i]); } return profit_2_out; };

随后，在第 5 天 (股票价格 = 0) 的时候买入，在第 6 天 (股票价格 = 3) 的时候卖出, 这笔交易所能获得利润 = 3-0 = 3 。

/* * @lc app=leetcode.cn id=188 lang=javascript * * [188] 买卖股票的最佳时机 IV */// @lc code=start /** * @param {number} k * @param {number[]} prices * @return {number} */ var maxProfit = function(k, prices) { let n = prices.length; if (k > n / 2) { k = Math.floor(n/2); } let profits = []; for(let j=0; j <= k; j++) { profits[j] = { profits_out: 0, profits_in: -prices[0] } }for( let i = 0; i < n; i++ ) { for( let j=1; j <= k; j++ ) { profits[j] = { profits_out: Math.max(profits[j][`profits_out`], profits[j][`profits_in`] + prices[i]), profits_in: Math.max(profits[j][`profits_in`], profits[j-1][`profits_out`] - prices[i]) } } }return profits[k][`profits_out`]; };

/* * @lc app=leetcode.cn id=309 lang=javascript * * [309] 最佳买卖股票时机含冷冻期 */// @lc code=start /** * @param {number[]} prices * @return {number} */ var maxProfit = function(prices) { let n = prices.length, profits_in = -prices[0], profits_out = 0, profits_freeze = 0; for( let i = 0; i < prices.length; i++ ) { let temp = profits_out; profits_out = Math.max(profits_out, prices[i] + profits_in); profits_in = Math.max(profits_in, profits_freeze - prices[i]); profits_freeze = temp; }return profits_out; };

/* * @lc app=leetcode.cn id=714 lang=javascript * * [714] 买卖股票的最佳时机含手续费 */// @lc code=start /** * @param {number[]} prices * @param {number} fee * @return {number} */ var maxProfit = function(prices, fee) { let n = prices.length, profits_in = 0 - prices[0], profits_out = 0; for( let i=0; i < prices.length; i++ ) { profits_out = Math.max(profits_out, prices[i] + profits_in - fee); profits_in = Math.max(profits_in, profits_out - prices[i]); }return profits_out < 0 ? 0 : profits_out; };

1. 股票问题关键在于对输入输出的状态进行判断转移，运用动态规划思想进行处理；
2. 在动态规划实现中比较常见的是多维数组的逐步迭代，对于股票问题可以进行降维处理，优化效率

/* * @lc app=leetcode.cn id=132 lang=javascript * * [132] 分割回文串 II */// @lc code=start /** * @param {string} s * @return {number} */ var minCut = function (s) { let j, dp = new Array(s.length).fill(s.length) for (let i = 0; i < s.length; i++) { j = 0 while (i - j >= 0 && i + j < s.length) { if (s[i - j] === s[i + j]) dp[i + j] = i - j === 0 ? 0 : dp[i + j] <= dp[i - j - 1] + 1 ? dp[i + j] : dp[i - j - 1] + 1 else break j++ } j = 0 while (i - j >= 0 && i + j + 1 < s.length) { if (s[i - j] === s[i + j + 1]) dp[i + j + 1] = i - j === 0 ? 0 : dp[i + j + 1] <= dp[i - j - 1] + 1 ? dp[i + j + 1] : dp[i - j - 1] + 1 else break j++ } } return dp[s.length - 1] };

/* * @lc app=leetcode.cn id=132 lang=javascript * * [132] 分割回文串 II */// @lc code=start /** * @param {string} s * @return {number} */ var minCut = function (s) { var manacher = function(s){ if(!s) return []; var lstRadios=[]; //拼装manacher字符串 s=s.replace(/\w/g,(a)=>{return '#'+a; })+'#'; //三个指针，现在先定义中心指针c和最右指针r,剩下一个就是运动指针了 var r=-1, c=-1; for(var i=0; ii?Math.min(lstRadios[2*c-i],r-i+1):1; while(i+lstRadios[i]-1){ if(s.charAt(i-lstRadios[i]) == s.charAt(i+lstRadios[i]))lstRadios[i]++; else break; }if(i+lstRadios[i]-1 > r){ r=1+lstRadios[i]-1; c=i; } } return lstRadios; }; if(s.length<=1) return 0; var lstRadios=manacher(s); var dp=[]; for(var i=0; i=0?(dp[i-j-1]+1):0),dp[i+j]); } //以i和i+1的中间为中心 d=lstRadios[2*i+2]/2; if(d<=0)continue; for(var j=1; j<=d; j++){ if(dp[i+j] == undefined) dp[i+j]=i+j; dp[i+j]=Math.min(((i-j)>=0?(dp[i-j]+1):0),dp[i+j]); } } return dp[s.length-1]; };

/* * @lc app=leetcode.cn id=132 lang=javascript * * [132] 分割回文串 II */// @lc code=start /** * @param {string} s * @return {number} */ var minCut = function(s) { const n = s.length; const g = new Array(n).fill(0).map(() => new Array(n).fill(true)); for (let i = n - 1; i >= 0; --i) { for (let j = i + 1; j < n; ++j) { g[i][j] = s[i] == s[j] && g[i + 1][j - 1]; } }const f = new Array(n).fill(Number.MAX_SAFE_INTEGER); for (let i = 0; i < n; ++i) { if (g[0][i]) { f[i] = 0; } else { for (let j = 0; j < i; ++j) { if (g[j + 1][i]) { f[i] = Math.min(f[i], f[j] + 1); } } } }return f[n - 1]; };

/* * @lc app=leetcode.cn id=1278 lang=javascript * * [1278] 分割回文串 III */// @lc code=start /** * @param {string} s * @param {number} k * @return {number} */ var palindromePartition = function(s, k) { const n = s.length; const dp = Array.from({length: n}, () => Array(k+1).fill(100)); const cost = Array.from({length: n}, () => Array(n).fill(0)); for (let len = 1; len < n; len++) { for (let i = 0; i < n - len; i++) { const j = i + len; cost[i][j] = cost[i+1][j-1] + (s[i] == s[j] ? 0 : 1); } }for (let i = 0; i < n; i++) { dp[i][1] = cost[0][i]; for (let kk = 2; kk <= k; kk++) { for (let j = 0; j < i; j++) { dp[i][kk] = Math.min(dp[i][kk], dp[j][kk-1] + cost[j+1][i]); } } }return dp[n-1][k]; };

/* * @lc app=leetcode.cn id=1278 lang=javascript * * [1278] 分割回文串 III */// @lc code=start /** * @param {string} s * @param {number} k * @return {number} */ var palindromePartition = function (s, k) { const m = s.length; const dp = Array.from(Array(k), () => Array(m)); const map = Array.from(Array(m), () => Array(m)); const helper = (i, j) => { const str = s.substring(i, j + 1); let res = 0; for (let l = 0; l < str.length / 2; l++) if (str[l] !== str[str.length - 1 - l]) res++; return res; }; for (let i = 0; i < m; i++) for (let j = i; j < m; j++) map[i][j] = helper(i, j); for (let i = 0; i < k; i++) { for (let j = i; j < m; j++) { if (i === j || i === 0) { dp[i][j] = map[i][j]; // No need to remove, each char is a substring continue; } let res = Infinity; for (let k = 1; j - k >= i - 1; k++) res = Math.min(res, map[j + 1 - k][j] + dp[i - 1][j - k]); dp[i][j] = res; } }return dp[k - 1][m - 1]; };

/* * @lc app=leetcode.cn id=1745 lang=javascript * * [1745] 回文串分割 IV */// @lc code=start /** * @param {string} s * @return {boolean} */ var checkPartitioning = function(s) { let dp = new Array(s.length); for (let i = 0; i < dp.length; i++) { dp[i] = new Array(s.length).fill(true); }for (let i = s.length - 1; i >=0 ; i--) { for (let j = i; j < s.length; j++) { if (i !== j) { dp[i][j] = (s[i] == s[j]) && dp[i + 1][j - 1]; } } } for (let i = 0; i < s.length - 2; i++) { if(dp[0][i] == false) continue; for (let j = i + 1; j < s.length - 1; j++) { if(dp[i+1][j] == false || dp[j + 1][s.length - 1] == false ) continue; if (dp[0][i] && dp[i + 1][j] && dp[j + 1][s.length - 1]) { return true; } } } return false; };

/* * @lc app=leetcode.cn id=139 lang=javascript * * [139] 单词拆分 */// @lc code=start /** * @param {string} s * @param {string[]} wordDict * @return {boolean} */ var wordBreak = function(s, wordDict) { const n = s.length; const wordDictSet = new Set(wordDict); const dp = new Array(n + 1).fill(false); dp[0] = true; for (let i = 1; i <= n; i++) { for (let j = 0; j < i; j++) { if (dp[j] && wordDictSet.has(s.substr(j, i - j))) { dp[i] = true; break; } } } return dp[n]; };

/* * @lc app=leetcode.cn id=140 lang=javascript * * [140] 单词拆分 II */// @lc code=start /** * @param {string} s * @param {string[]} wordDict * @return {string[]} */ var wordBreak = function(s, wordDict) { let dp = new Array(s.length + 1).fill(false) dp[0] = true for (let i = 1; i <= s.length; i++) { for (let j = 0; j <= i; j++) { if (dp[j] && wordDict.indexOf(s.slice(j, i)) >= 0) { dp[i] = true break } } } if(!dp[s.length]) return [] let ans = [] function backTrack(cur, str) { if(str.length == 0) { ans.push(cur) return } for(let i = 0; i < str.length; i++) { if(wordDict.indexOf(str.slice(0, i + 1)) >= 0) { if(cur.length > 0) backTrack(cur + ' ' + str.slice(0, i + 1), str.slice(i + 1)) else backTrack(str.slice(0, i + 1), str.slice(i + 1)) } } } backTrack('', s) return ans };

/* * @lc app=leetcode.cn id=140 lang=javascript * * [140] 单词拆分 II */// @lc code=start /** * @param {string} s * @param {string[]} wordDict * @return {string[]} */ var wordBreak = function(s, wordDict) { // 辅助函数 const backtrack = (s, length, wordSet, index, map) => { if (map.has(index)) { return map.get(index); } const wordBreaks = []; if (index === length) { wordBreaks.push([]); } for (let i = index + 1; i <= length; i++) { const word = s.substring(index, i); if (wordSet.has(word)) { const nextWordBreaks = backtrack(s, length, wordSet, i, map); for (const nextWordBreak of nextWordBreaks) { const wordBreak = [word, ...nextWordBreak] wordBreaks.push(wordBreak); } } } map.set(index, wordBreaks); return wordBreaks; }const map = new Map(); const wordBreaks = backtrack(s, s.length, new Set(wordDict), 0, map); const breakList = []; for (const wordBreak of wordBreaks) { breakList.push(wordBreak.join(' ')); } return breakList; };

/* * @lc app=leetcode.cn id=343 lang=javascript * * [343] 整数拆分 */// @lc code=start /** * @param {number} n * @return {number} */ var integerBreak = function(n) { // 利用均值不等式 x1 * x2 * ··· * xn ≤ ( ( x1 + x2 + ··· + xn ) / n )^n let max = -Infinity; for( let i = 2; i <= n; i++ ) { let v = -Infinity; if(n % i == 0) { v = Math.pow(n/i,i) } else { let v1 = Math.ceil(n/i), v2 = Math.floor(n/i) v = Math.max( Math.pow(v1,i-1) * (n - v1*(i-1)) , Math.pow(v2,i-1) * (n - v2*(i-1)) ) } max = Math.max(v, max) } return max; };

/* * @lc app=leetcode.cn id=343 lang=javascript * * [343] 整数拆分 */// @lc code=start /** * @param {number} n * @return {number} */ var integerBreak = function(n) { const dp = new Array(n + 1); dp[1] = 1; dp[2] = 1; for (let i = 3; i <= n; i++) { dp[i] = 0; // 对于数字 i，它可以分为两份：j 和 i-j，j 的范围是 1 到 i-j for (let j = 1; j <= i - j; j++) { // 对于 i-j 这部分可以拆或不拆，不拆就是 i-j，拆就是 dp[i-j] dp[i] = Math.max(dp[i], j * (i - j), j * dp[i - j]); } } return dp[n]; };

/* * @lc app=leetcode.cn id=410 lang=javascript * * [410] 分割数组的最大值 */// @lc code=start /** * @param {number[]} nums * @param {number} m * @return {number} */ var splitArray = function(nums, m) { let max = 0 sum = 0; for (let i = 0; i < nums.length; i++) { if (max < nums[i]) max = nums[i]; sum += nums[i]; }while (max < sum) { let mid = parseInt((sum - max) / 2, 10) + max; // 随机选择的值成立则这个值默认为最大的可能结果继续查找 if (check(nums, mid, m)) { sum = mid; } else { // 不满足，重置最小可能结果 max = mid + 1; } }function check(nums, val, m) { let sum = 0, index = 1; for (let i = 0; i < nums.length; i++) { // 如果分段和大于了假设的结果说明，i是该分段的终点，形成一个分段 // index记录+1，i就成了下一个分段的起点（重置sum）开始校验下一个分段 if (sum + nums[i] > val) { index++; sum = nums[i]; } else { sum += nums[i]; } } // 如果index即分段数量满足小于等于m则说明这个假设值成立 return index <= m; }// 返回最小可能结果 return max; };

/* * @lc app=leetcode.cn id=410 lang=javascript * * [410] 分割数组的最大值 */// @lc code=start /** * @param {number[]} nums * @param {number} m * @return {number} */ var splitArray = function(nums, m) { let len = nums.length, sumList = Array(len + 1).fill(0), dp = Array.from({ length: len + 1 }, () => Array(m + 1).fill(Number.MAX_VALUE)); // 逐位增加，反面后面根据区间求区间和 for (let i = 0; i < len; i++) { sumList[i + 1] = sumList[i] + nums[i]; }// 默认值 dp[0][0] = 0; for (let i = 1; i <= len; i++) { for (let j = 1; j <= Math.min(m, i); j++) { // 前i个数分成j段 for (let x = j - 1; x < i; x++) { // x最后一段的起点 // perv本轮分割完成 分段中最大的和 let prev = Math.max(dp[x][j - 1], sumList[i] - sumList[x]) // 该分割情况下最大分段和的最小值 dp[i][j] = Math.min(prev, dp[i][j]) } } }return dp[len][m] };

?
如果满足以下条件，则称子数组(P, Q)为等差数组：
?
元素 A[P], A[p + 1], ..., A[Q - 1], A[Q] 是等差的。并且 P + 1 < Q 。
?
函数要返回数组 A 中所有为等差数组的子数组个数。
?

?
示例:
?
A = [1, 2, 3, 4]
?
返回: 3, A 中有三个子等差数组: [1, 2, 3], [2, 3, 4] 以及自身 [1, 2, 3, 4]。
?
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/arithmetic-slices
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
方案一：

/* * @lc app=leetcode.cn id=413 lang=javascript * * [413] 等差数列划分 */// @lc code=start /** * @param {number[]} nums * @return {number} */ var numberOfArithmeticSlices = function(nums) { // 判断是否是等差数列 const isArithmetic = arr => { const diff = arr[1] - arr[0]; for( let p = 0, q = p+ 1; p < arr.length -1; p++, q++ ) { if( arr[q] - arr[p] != diff ) { return false; } } return true; } // 返回的个数 let n = 0; for(let a = 0; a < nums.length - 2; a++ ) { for(let b = a + 2; b < nums.length; ) { if(!isArithmetic(nums.slice(a,b+1))) { break; } else { n++; b++ } } }return n; };

方案二：

/* * @lc app=leetcode.cn id=413 lang=javascript * * [413] 等差数列划分 */// @lc code=start /** * @param {number[]} nums * @return {number} */ var numberOfArithmeticSlices = function(nums) { let len = nums.length if (len < 3) { return 0 } let dp = Array(len).fill(0) for (let i = 2; i <= len; i++) { if (nums[i] - nums[i - 1] === nums[i - 1] - nums[i - 2]) { dp[i] = dp[i - 1] + 1 } } return dp.reduce((prev, cur) => { return prev + cur }, 0) };

有两种方案：1、暴解；2、动态规划
2021.07.12
No.416 分割等和子集 给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。?

?
示例 1：
?
输入：nums = [1,5,11,5]
输出：true
解释：数组可以分割成 [1, 5, 5] 和 [11] 。
示例 2：
?
输入：nums = [1,2,3,5]
输出：false
解释：数组不能分割成两个元素和相等的子集。

?
提示：
?
1 <= nums.length <= 200
1 <= nums[i] <= 100
?
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/partition-equal-subset-sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
方案：

/* * @lc app=leetcode.cn id=416 lang=javascript * * [416] 分割等和子集 */// @lc code=start /** * @param {number[]} nums * @return {boolean} */ var canPartition = function(nums) { if(nums.length < 2) return false; const sum = nums.reduce((prev, curr) => prev + curr); if( sum % 2 !== 0) { return false; } const target = sum / 2; nums.sort((a,b) => b-a); if(nums[0] > target) { return false; } // 动态规划 const dp = new Array(nums.length).fill(0).map(v => new Array(target + 1, false)); for (let i = 0; i < nums.length; i++) { dp[i][0] = true; } dp[0][nums[0]] = true; for (let i = 1; i < nums.length; i++) { const num = nums[i]; for (let j = 1; j <= target; j++) { if (j >= num) { dp[i][j] = dp[i - 1][j] | dp[i - 1][j - num]; } else { dp[i][j] = dp[i - 1][j]; } } } return dp[nums.length - 1][target]; };

NP完全，可转化为0-1背包问题，动态规划解决
2021.07.13
No.446 等差数列拆分 ii-子序列 如果一个数列至少有三个元素，并且任意两个相邻元素之差相同，则称该数列为等差数列。?
例如，以下数列为等差数列:
?
1, 3, 5, 7, 9
7, 7, 7, 7
3, -1, -5, -9
以下数列不是等差数列。
?
1, 1, 2, 5, 7

?
数组 A 包含 N 个数，且索引从 0 开始。该数组子序列将划分为整数序列 (P0, P1, ..., Pk)，满足 0 ≤ P0 < P1 < ... < Pk < N。
?

?
如果序列 A[P0]，A[P1]，...，A[Pk-1]，A[Pk] 是等差的，那么数组 A 的子序列 (P0，P1，…，PK) 称为等差序列。值得注意的是，这意味着 k ≥ 2。
?
函数要返回数组 A 中所有等差子序列的个数。
?
输入包含 N 个整数。每个整数都在 -231 和 231-1 之间，另外 0 ≤ N ≤ 1000。保证输出小于 231-1。
?

?
示例：
?
输入：[2, 4, 6, 8, 10]
?
输出：7
?
解释：
所有的等差子序列为：
[2,4,6]
[4,6,8]
[6,8,10]
[2,4,6,8]
[4,6,8,10]
[2,4,6,8,10]
[2,6,10]
?
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/arithmetic-slices-ii-subsequence
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
方案：

/* * @lc app=leetcode.cn id=446 lang=javascript * * [446] 等差数列划分 II - 子序列 */// @lc code=start /** * @param {number[]} nums * @return {number} */ var numberOfArithmeticSlices = function(nums) { // 定义 i 的数组 let dp = Array(nums.length).fill(0).map(x=> new Object()) let ans = 0 for(let i=1; i

动态规划
2021.07.14
No.698 划分为k个相等的子集 给定一个整数数组nums 和一个正整数 k，找出是否有可能把这个数组分成 k 个非空子集，其总和都相等。?
示例 1：
?
输入： nums = [4, 3, 2, 3, 5, 2, 1], k = 4
输出： True
说明： 有可能将其分成 4 个子集（5），（1,4），（2,3），（2,3）等于总和。

?
提示：
?
1 <= k <= len(nums) <= 16
0 < nums[i] < 10000
?
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/partition-to-k-equal-sum-subsets
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
方案一：

/* * @lc app=leetcode.cn id=698 lang=javascript * * [698] 划分为k个相等的子集 */// @lc code=start /** * @param {number[]} nums * @param {number} k * @return {boolean} */ var canPartitionKSubsets = function(nums, k) { const sum = nums.reduce((prev, curr) => prev + curr); if( sum % k !== 0 ) return false; const target = sum / k; nums.sort((a,b) => b - a); if(nums[0] > target) return false; // 动态规划 const MAX_STATE = (1 << nums.length) - 1 // 1 <= N <= 16 let dp = new Array(MAX_STATE + 1).fill(null) dp[0] = 0// 枚举所有状态，递推 for (let state = 1; state <= MAX_STATE; ++state) { // O(2^N) for (let i = 0; i < nums.length; ++i) { // O(N) const iBit = 1 << i // 如果 state 表示未选取 nums[i] ，说明不能达到 (state, i) 状态 if ((state & iBit) === 0) continueconst prevState = state ^ iBit // NOTICE: 如果不能到达 prevState 状态 if (dp[prevState] === null) continue const prevSubsetSum = dp[prevState] % target // 最优性剪枝优化：nums 已升序排序，如果 nums[i] 已偏大，后续更加偏大，无需尝试 if (prevSubsetSum + nums[i] > target) break dp[state] = dp[prevState] + nums[i] } }// console.log(dp) return dp[MAX_STATE] === sum };

方案二：

/* * @lc app=leetcode.cn id=698 lang=javascript * * [698] 划分为k个相等的子集 */// @lc code=start /** * @param {number[]} nums * @param {number} k * @return {boolean} */ var canPartitionKSubsets = function(nums, k) { const sum = nums.reduce((prev, curr) => prev + curr); if( sum % k !== 0 ) return false; const target = sum / k; nums.sort((a,b) => b - a); if(nums[0] > target) return false; // 回溯 const sums = new Array(k).fill(0); const helper = (i, sums, target, nums, k) => { if(i === nums.length) return true; for( let j = 0; j< k; j++ ) { if(sums[j] < target && nums[i] + sums[j] <= target) { sums[j] += nums[i]; if(helper(i+1, sums, target, nums, k)) { return true; } sums[j] -= nums[i]; } }return false; }return helper(0,sums, target, nums, k); };

有两种方案：1、动态规划，用二进制对数组进行表示；2、回溯递归
2021.07.15
No.902 最大为N的数字组合 我们有一组排序的数字 D，它是{'1','2','3','4','5','6','7','8','9'} 的非空子集。（请注意，'0' 不包括在内。）?
现在，我们用这些数字进行组合写数字，想用多少次就用多少次。例如 D = {'1','3','5'}，我们可以写出像 '13', '551', '1351315' 这样的数字。
?
返回可以用 D 中的数字写出的小于或等于 N 的正整数的数目。
?

?
示例 1：
?
输入：D = ["1","3","5","7"], N = 100
输出：20
解释：
可写出的 20 个数字是：
1, 3, 5, 7, 11, 13, 15, 17, 31, 33, 35, 37, 51, 53, 55, 57, 71, 73, 75, 77.
示例 2：
?
输入：D = ["1","4","9"], N = 1000000000
输出：29523
解释：
我们可以写 3 个一位数字，9 个两位数字，27 个三位数字，
81 个四位数字，243 个五位数字，729 个六位数字，
2187 个七位数字，6561 个八位数字和 19683 个九位数字。
总共，可以使用D中的数字写出 29523 个整数。

?
提示：
?
D 是按排序顺序的数字 '1'-'9' 的子集。
1 <= N <= 10^9
?
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/numbers-at-most-n-given-digit-set
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
方案一：

/* * @lc app=leetcode.cn id=902 lang=javascript * * [902] 最大为 N 的数字组合 */// @lc code=start /** * @param {string[]} digits * @param {number} n * @return {number} */ var atMostNGivenDigitSet = function(digits, n) { digits.sort((a,b) => Number(a) - Number(b)) // 获取n的位数 const UNIT = (n + '').length; console.log('UNIT', UNIT) // 获取n对应位置数组 const queue = (n + '').split(''); let sum = 0; for(let i = 1; i < UNIT; i++) { sum += Math.pow(digits.length, i) } // 辅助函数 const helper = (pos, queue, digits) => { if (pos === queue.length) { return 1; }let count = 0; for (let i = 0; i < digits.length; i++) { if (digits[i] < queue[pos]) { count += Math.pow(digits.length, queue.length - pos - 1); } else if (digits[i] == queue[pos]) { count += helper(pos + 1, queue, digits); } else { break; } }return count; }sum += helper(0, queue, digits)return sum; };

方案二：

/* * @lc app=leetcode.cn id=902 lang=javascript * * [902] 最大为 N 的数字组合 */// @lc code=start /** * @param {string[]} digits * @param {number} n * @return {number} */ var atMostNGivenDigitSet = function(digits, n) { const s = n + ''; const K = s.length; const dp = new Array(K+1).fill(0); dp[K] = 1; for(let i = K -1; i >= 0; --i) { let si = s[i]; for(let j=0; j < digits.length; j++) { if(digits[j] < si) { dp[i] += Math.pow(digits.length, K-i-1) } else if(digits[j] == si) { dp[i] += dp[i+1]; } } }for(let k=1; k< K; ++k) { dp[0] += Math.pow(digits.length, k) }return dp[0] };

有两种方案：1、递归；2、动态规划
2021.07.16
No.923 三数之和的多种可能 给定一个整数数组 A，以及一个整数 target 作为目标值，返回满足 i < j < k 且 A[i] + A[j] + A[k] == target 的元组 i, j, k 的数量。?
由于结果会非常大，请返回 结果除以 10^9 + 7 的余数。
?

?
示例 1：
?
输入：A = [1,1,2,2,3,3,4,4,5,5], target = 8
输出：20
解释：
按值枚举（A[i]，A[j]，A[k]）：
(1, 2, 5) 出现 8 次；
(1, 3, 4) 出现 8 次；
(2, 2, 4) 出现 2 次；
(2, 3, 3) 出现 2 次。
示例 2：
?
输入：A = [1,1,2,2,2,2], target = 5
输出：12
解释：
A[i] = 1，A[j] = A[k] = 2 出现 12 次：
我们从 [1,1] 中选择一个 1，有 2 种情况，
从 [2,2,2,2] 中选出两个 2，有 6 种情况。

?
提示：
?
3 <= A.length <= 3000
0 <= A[i] <= 100
0 <= target <= 300
?
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/3sum-with-multiplicity
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
方案：

/* * @lc app=leetcode.cn id=923 lang=javascript * * [923] 三数之和的多种可能 */// @lc code=start /** * @param {number[]} arr * @param {number} target * @return {number} */ var threeSumMulti = function(arr, target) { console.log('arr', arr.length) // mod数 const mod = (10**9)+7; // 阶乘 const factorial = n => { if (0 === n) { return 1; } let res = 1; for (let i = 1; i <= n; ++i) { res *= i; } return res; } // Cmn函数 const combination = (m,n) => { let s = 1; for(let i =0; i< n; i++) { s *= (m - i); } return s / factorial(n) } console.log('combination', combination(3000,3)) // 数组去重 并按从小到大排序 const _ = Array.from(new Set(arr)).sort((a,b) => a-b); const LEN = _.length, MAX = _[LEN-1], MIN = _[0]; console.log('_', _) // 在去重数组中去选择符合要求的三个数 let i = 0, j = LEN - 1, m = ~~((i+j)/2); // r用于存储符合要求的数组 const r = []; for(let i=0; i < LEN; i++) { let j= LEN -1; for(let m = i; m <= j; ) { if(_[i]+_[m]+_[j] == target) { r.push([_[i], _[m], _[j]]) } if(_[i]+_[m]+_[j]>target && m < j) { j--; m-- } m++ } } console.log('r', r) // 构建值对应数量的map const map = {}; for(let num = 0; num < LEN; num++) { let key = _[num], value = https://www.it610.com/article/arr.filter(f => f == key).length; map[key] = value; } console.log('map', map) // 对r进行排查 let sum = 0; r.forEach(item => { if(item[0] == item[1] && item[1] == item[2]) { if(map[`${item[0]}`] >= 3) { console.log('走了 A A A') sum += combination(map[`${item[0]}`], 3) } } else if(item[0] != item[1] && item[1] == item[2]) { if(map[`${item[1]}`] >= 2) { console.log('走了 A B B') sum += combination(map[`${item[0]}`], 1)*combination(map[`${item[1]}`], 2) } } else if(item[0] == item[1] && item[1] != item[2]) { if(map[`${item[0]}`] >= 2) { console.log('走了 A A B') sum += combination(map[`${item[0]}`], 2)*combination(map[`${item[2]}`], 1) } } else if(item[0] != item[1] && item[1] != item[2] && item[0] != item[2]) { console.log('走了 A B C') sum += combination(map[`${item[0]}`], 1)*combination(map[`${item[1]}`], 1)*combination(map[`${item[2]}`], 1) } }) console.log('sum', sum) return sum % mod; };

三指针法，阶乘可进行动态规划实现
总结：

1. 拆分组合问题关键在于对问题的转移方程定义及建模，将状态可以逐步转移，从而解决问题；
2. 在状态方程建立过程中，常常需要结合其他常见方法如指针、递归等方法来进行优化

?
【前端常见算法题(动态规划篇)】
文章图片

推荐阅读

• 

  南宁：房贷利率新政实施后买房能省多少钱？
• 

  drive|希捷推出 Xbox 专用外置 SSD：1TB 约 1095元，USB 3.2 Gen1 接口
• 

  农户贷款如何界定 「一般农户指什么」
• 

  java用什么软件写代码，JAVA用什么软件编写
• 

  不要吃发物 不要吃过甜过咸和酸性的食物
• 

  八角金盘的介绍-八角金盘的作用
• 

  flutter添加横线，flutter虚线边框
• 

  为什么戒烟后会发胖？
• 

  佛珠多肉烂根怎么办 佛珠多肉烂了怎么办
• 

  中国知名菜刀有什么牌子？中国十大菜刀品牌排行
• 

  从入门到精通，轻松应对各种错误 打印机1700代码解析
• 

  水果礼盒制作步骤大全图解 水果礼盒的制作技巧是怎么样的
• 

  支付宝花呗当面花怎么使用？使用方法及店铺详细介绍
• 

  恒为科技的军方服务器具有怎样的性能？ 恒为科技军方服务器怎么样
• 

  gis中画的图成无效的书签，gis图没了
• 

  工商银行主要业务有哪些
• 

  iphone皮套
• 

  爱普生1430喷墨机清零
• 

  关于vb.neteval的信息
• 

  非诚勿扰影视产业分析

• 画解算法（1.|画解算法：1. 两数之和）
• Guava|Guava RateLimiter与限流算法
• 唱歌教学（导致嗓音损坏的几个常见的错误唱歌方法！）
• Hive常见问题汇总
• 一个选择排序算法
• SG平滑轨迹算法的原理和实现
• Jsr303做前端数据校验
• 《算法》-图[有向图]
• JS常见数组操作补充
• LeetCode算法题-11.|LeetCode算法题-11. 盛最多水的容器（Swift）