移除最少字符使字符串升序的递归解法内存优化咨询

Hey there! Let's break down your problem and fix that memory-heavy recursive approach. First off, your core task is actually a classic Longest Increasing Subsequence (LIS) problem—since the minimum number of characters to remove equals the total string length minus the length of the longest valid ascending subsequence. Storing every possible path is totally unnecessary, so let's optimize this.

Your Original Code & Memory Issue #

You mentioned your recursive code works but uses too much memory because it saves all valid subsequences in pushRes. For a string of length n, there can be up to 2^n possible subsequences—this blows up fast even for moderately long strings.

Here's your original code for reference:

/** 
 * Returns true of false, indicating whether the given array of numbers is sorted 
 * isSorted([]) // true 
 * isSorted([-Infinity, -5, 0, 3, 9]) // true 
 * isSorted([3, 9, -3, 10]) // false 
 * 
 * @param {number[]} arr 
 * @return {boolean} 
 */ 
function isSorted(arr) { 
  const limit = arr.length - 1; 
  return arr.every((_, i) => (i < limit ? arr[i] <= arr[i + 1] : true)); 
} 

function myrec(arr) { 
  var pushRes = []; 
  var rec = function(arr, res=[]) { 
    if(arr.length == 0) { 
      pushRes.push(res); 
      return; 
    } 
    for(var i=0; i<arr.length; i++) { 
      // copy 
      var tmpArr = arr.slice(); 
      // get 1 letter 
      var curr = tmpArr.splice(i, 1); 
      // rest 
      var nextArr = tmpArr.slice(); 
      var condi = isSorted(nextArr); 
      var tmp; 
      if(condi) { 
        tmp = res.concat(curr); 
        pushRes.push(tmp); 
        return; 
      } else { 
        tmp = res.concat(curr); 
        rec(nextArr, tmp); 
      } 
    } 
  } 
  rec(arr); 
  return pushRes; 
} 

function myfind(input) { 
  var arr = input.split(''); 
  var res = myrec(arr); 
  var min = Number.MAX_SAFE_INTEGER; 
  for(var i=0; i<res.length; i++) { 
    var num = res[i].length; 
    if(num < min) { 
      min = num; 
    } 
  } 
  return input.length - min; // Corrected to return removal count
} 

var input = "banana"; 
//var input = "aaaaaaz"; 
var out = myfind(input); 
console.log(out); 

Optimization 1: Recursive Approach Without Storing All Paths #

Instead of saving every valid subsequence, modify your recursive function to track only the length of the longest valid subsequence encountered. This cuts memory usage from O(2^n) to O(n) (just the recursion stack depth).

function longestIncreasingSubsequence(arr, prevChar = '', currentLength = 0) {
  if (arr.length === 0) {
    return currentLength;
  }
  
  let maxLength = currentLength;
  
  // Try including or excluding each character
  for (let i = 0; i < arr.length; i++) {
    const currChar = arr[i];
    // Option 1: Include current character if it maintains order
    if (currChar >= prevChar) {
      const remaining = arr.slice(i + 1);
      const newLength = longestIncreasingSubsequence(remaining, currChar, currentLength + 1);
      maxLength = Math.max(maxLength, newLength);
    }
    // Option 2: Exclude current character entirely
    const remaining = arr.slice(i + 1);
    const newLength = longestIncreasingSubsequence(remaining, prevChar, currentLength);
    maxLength = Math.max(maxLength, newLength);
  }
  
  return maxLength;
}

function myfindOptimized(input) {
  const arr = input.split('');
  const lisLength = longestIncreasingSubsequence(arr);
  return input.length - lisLength;
}

const input = "banana";
console.log(myfindOptimized(input)); // Outputs 3, correct

Optimization 2: Dynamic Programming (Faster & More Efficient) #

The recursive approach still has O(2^n) time complexity, which is slow for longer strings. Dynamic programming (DP) brings this down to O(n²) time and O(n) space—way more efficient.

DP Logic: #

• Define dp[i] as the length of the longest increasing subsequence ending at the i-th character
• Initialize each dp[i] = 1 (each character is a subsequence of length 1 by itself)
• For each character i, check all previous characters j: if s[j] <= s[i], update dp[i] = max(dp[i], dp[j] + 1)
• The maximum value in dp is the length of the LIS

function myfindDP(input) {
  const s = input.split('');
  const n = s.length;
  if (n === 0) return 0;
  
  const dp = new Array(n).fill(1);
  
  for (let i = 1; i < n; i++) {
    for (let j = 0; j < i; j++) {
      if (s[j] <= s[i]) {
        dp[i] = Math.max(dp[i], dp[j] + 1);
      }
    }
  }
  
  const lisLength = Math.max(...dp);
  return input.length - lisLength;
}

const input = "banana";
console.log(myfindDP(input)); // Outputs 3, correct

Key Takeaways #

• Your original approach wastes memory by storing every possible subsequence—you only need to track the longest one
• For recursive solutions, return the length of the longest valid subsequence instead of saving all paths
• Dynamic programming is the best approach here for both time and space efficiency
• Remember the core relationship: Minimum characters to remove = Total string length - Length of LIS

内容的提问来源于stack exchange，提问作者kenpeter