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
投递美团等公司10个岗位 >
