javascript - 从字符串中删除最少的字母，使其按升序排列

Question

目前，我正在学习动态规划。这是我看到有人问的问题之一

假设输入“banana”，我们返回3。3是从“banana”中删除的最少字母数。例如aan，则按升序排列。

下面的代码可以工作，但我基本上存储所有可能的路径并找到路径的最小数量。

我的问题是，这是一种在内存中存储较少路径的方法吗？即里面pushRes = [];

/**
  * 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 min;
}


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

Answer 1

这可以通过最长升序子序列减去输入字符串的长度来完成。

function getLongestAscendingSubsequence (input) {
  let arr = [];
  for (let i = 0; i < input.length; i++) {
    arr.push(0);
  }
  arr[0] = 1;
  for (let i = 1; i < input.length; i++) {
    if (input[i] >= input[i - 1]) {
      arr[i] = arr[i - 1] + 1;
    } else {
      let found = false;
      for (let j = i - 1; j >= 0; j--) {
        if (input[j] <= input[i]) {
          arr[i] = arr[j] + 1;
          found = true;
          break;
        }
      }
      if (!found) {
        arr[i] = 1;
      }
    }
  }
  return input.length - Math.max(...arr);
}