DP编程题思路统览

(顺序不代表什么,由于shift代价比较高，所以使用队列数据结构的，有些用了map代替) 需要多次shift的都采用splice或者slice

一、跳台阶（跳跃题）

描述：每次只能跳一次或者两次，计算所有跳的方法的次数。
思路：我们从最后一次到达的台阶想，其实最后一次的方法就是“从倒数第一个台阶跳过来的方法”+“从倒数第二个台阶跳过来的方法”(主要是因为只能跳一个和两个，比较特殊)，于是动态方程就是dp[i] = dp[i-1]+dp[i-2]。
接下来就是初始化：dp[0] = 1; dp[1]=2; (跳到第一个台阶只有一个方法，跳到第二个台阶有两个方法)
最终的结果：dp[nums.length-1]

二、跳跃方法数（跳跃题--限定跳跃次数以及固定到达位置）

描述：给定数组（固定了每个位置能跳跃到的地方），如[[0, 2], [0, 4], [2, 1], [1, 3], [4, 1], [2, 3], [3, 4]]
思路：将每跳一步作为一个大状态-->使用一个数组存储每跳一步到达位置的下标(没跳一步都要判断是否到达终点，到达就count++)-->再依次取数组，根据位置的不同继续走下一步，同是第n步，就都放入另一个数组里（必须是另一个数组，不然无法知道前一个数组是否结束遍历）（这里可以用map优化存储到达这个位置的次数）-->跳完n步后结束循环
初始化：一个空数组[]，一个方法总次数count=0
结果：count

 function chuan(n, arr, k) {
            let flags = new Map();
            for (let i = 0; i < arr.length; i++) {
                let current = arr[i];
                if (flags.has(current[0])) {
                    flags.get(current[0]).push(current[1])
                }
                else {
                    flags.set(current[0], [current[1]])
                }
            }
            let queueMap = new Map();
            flags.get(0).forEach((v, i) => {
                queueMap.set(v, 1)
            })
            let res = 0;
            for (let i = 0; i < k; i++) {
                let key, value;
                let nextqueueMap = new Map();
                for ([key, value] of queueMap) {
                    if (key === n - 1) {
                        res += value;
                    }
                    flags.get(key).forEach((v, i) => {
                        if (nextqueueMap.has(v)) {
                            nextqueueMap.delete(v)
                            nextqueueMap.set(v,nextqueueMap.get(v)+1)
                        } else {
                            nextqueueMap.set(v, 1)
                        }
                    })
                }
                queueMap = nextqueueMap;
            }

             return res
        }

三、最小跳跃次数（跳跃题--限定跳跃次数）

描述：给定数组，如[2, 3, 1, 1, 4]，求最小跳跃次数
思路：遍历所有值，每遍历一个，就要根据它的跳跃数去更新能到达的位置的dp，也就是比较dp[i+count]和dp[i]+1（i为当前遍历位置的下标,count为1~nums[i]当前跳跃数之间的值）(这里还要判断是否下标溢出)
初始化：dp=[],需要遍历存储infinity（便于后续比较）
结果： dp[nums.length-1]
(如果为infinity就是不能到达)

 function jump(nums) {
            let dp = [0];
            for (let i = 1; i < nums.length; i++) {
                dp.push(Infinity)
            }
            for (let i = 0; i < nums.length; i++) {
                if (nums[i]) {
                    for (let j = 1; j <= nums[i]; j++) {
                        if (i + j <= nums.length - 1) {
                            dp[i + j] = Math.min((dp[i] + 1), dp[i + j]);
                        }
                        else {
                            break;
                        }
                    }
                }
            }
            if (dp[nums.length - 1] === Infinity) {
                return 0
            }
            else {
                return dp[nums.length - 1]
            }
        }

四、连续子数组的最大值

思路：由于是连续，dp[i]=Math.max(dp[i-1]+dp[i],dp[i]),前面位置的最大值和后面的一定是有密切关系.

//普通思路
function FindGreatestSumOfSubArray(array)
{
            let dp = [array[0]];
            for (let i = 1; i < array.length; i++) {
                dp[i] =  Math.max(dp[i-1]+array[i],array[i])
            }
            return Math.max(...dp)
}

//这个优化了内存，用一个tempsum代替了dp数组
function FindGreatestSumOfSubArray(array)
{
            let map = new Map();
            let max = array[0];
            let tempsum = 0
            for (let i = 0; i < array.length; i++) {
                tempsum += array[i];
                max = Math.max(max, tempsum)
                if(tempsum<0) tempsum = 0
            }
            return max
}

五、最长无重复子数组

思路：方一：使用栈，然后判断后shift 方二：使用map，判断后循环delete（复杂度高，会超时）方三：使用map，更新value就好了，会遇到之前的值，需要和left进行比对，超出left则舍弃。

function maxLength(arr) {
            var map = new Map();
            let left = 0;
            let maxLength = 0;
            for (let right = 0; right < arr.length; right++) {
                let templeft = map.has(arr[right])
                if (templeft) {
                    left = Math.max(left,map.get(arr[right]) + 1)
                }
                maxLength = Math.max(maxLength, right - left + 1)
                map.set(arr[right], right);
            }
            return maxLength;
}

六、最长递增子序列（不连续）

思路：简单说就是一个dp，每个位置都会有当前最大的递增子序列长度，当遇到小于前面的值时，去前面寻找所有小于他的值，比对dp，更新dp