动静布局的基础知识
- 爬楼梯的起码老本
一个数组 cost 的所有数字都是负数，它的第 i 个数字示意在一个楼梯的第 i 级台阶往上爬的老本，在领取了老本 cost[i]之后能够从第 i 级台阶往上爬 1 级或 2 级。假如台阶至多有 2 级，既能够从第 0 级台阶登程，也能够从第 1 级台阶登程，请计算爬上该楼梯的起码老本。例如，输出数组[1，100，1，1，100，1]，则爬上该楼梯的起码老本是 4，别离通过下标为 0、2、3、5 的这 4 级台阶，如图 14.1 所示。
函数 f（i） 示意从楼梯的第 i 级台阶再往上爬的起码老本
f(i) = min(f(i-1), f(i-2)) + cost[i]/**
* @param {number[]} cost
* @return {number}
*/
var minCostClimbingStairs = function (cost) {
let len = cost.length;
const dp = new Array(len + 1);
dp[0] = dp[1] = 0;
for (let i = 2; i <= len; i++) {dp[i] = Math.min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
}
return dp[len];
};单序列问题
单序列问题是与动静布局相干的问题中最有可能在算法面试中遇到的题型。这类题目都有适宜使用动静布局的问题的特点，如解决问题须要若干步骤，并且每个步骤都面临若干抉择，须要计算解的数目或最优解。除此之外，这类题目的输出通常是一个序列，如一个一维数组或字符串。
利用动静布局解决单序列问题的要害是每一步在序列中减少一个元素，依据题目的特点找出该元素对应的最优解（或解的数目）和后面若干元素（通常是一个或两个）的最优解（或解的数目）的关系，并以此找出相应的状态转移方程。一旦找出了状态转移方程，只有留神防止不必要的反复计算，问题就能迎刃而解。
- 屋宇盗窃
输出一个数组示意某条街道上的一排房屋内财产的数量。如果这条街道上相邻的两幢屋宇被盗就会主动触发报警零碎。请计算小偷在这条街道上最多能偷取到多少财产。例如，街道上 5 幢房屋内的财产用数组 [2，3，4，5，3] 示意，如果小偷到下标为 0、2 和 4 的房屋内偷盗，那么他能偷取到价值为 9 的财物，这是他在不触发报警零碎的状况下能偷取到的最多的财物.
`f(i)` 示意能偷取的最多财物
f(0) = arr[0]
f(1) = Math.max(arr[0], arr[1])
f(2) = Math.max(f(0) + arr[2], f(1))
f(3) = Math.max(f(2), f(1)+arr[3])/**
* @param {number[]} nums
* @return {number}
*/
var rob = function (nums) {
let len = nums.length;
const dp = new Array(len);
dp[0] = nums[0];
dp[1] = Math.max(nums[0], nums[1]);
for (let i = 2; i < len; i++) {dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
}
return dp[len - 1];
};第一次本人写进去，不须要看题解，果然这货色须要练习。
思考到每间屋宇的最高总金额只和该屋宇的前两间屋宇的最高总金额相干，因而能够应用滚动数组，在每个时刻只须要存储前两间屋宇的最高总金额。
/**
* @param {number[]} nums
* @return {number}
*/
var rob = function (nums) {
let len = nums.length;
if(len == 0) return 0
if (len == 1) {return nums[0];
}
const dp = new Array(2);
dp[0] = nums[0];
dp[1] = Math.max(nums[0], nums[1]);
for (let i = 2; i < len; i++) {dp[i % 2] = Math.max(dp[(i-1)%2], dp[(i-2)%2] + nums[i]);
}
return dp[(len-1)%2]
};
- 环形屋宇盗窃
一个业余的小偷，打算偷窃一个环形街道上沿街的屋宇，每间房内都藏有肯定的现金。这个中央所有的屋宇都 围成一圈，这意味着第一个屋宇和最初一个屋宇是紧挨着的。同时，相邻的屋宇装有互相连通的防盗零碎，如果两间相邻的屋宇在同一早晨被小偷闯入，零碎会主动报警。
/**
* @param {number[]} nums
* @return {number}
*/
var rob = function(nums) {
const length = nums.length;
if (length === 1) {return nums[0];
} else if (length === 2) {return Math.max(nums[0], nums[1]);
}
return Math.max(robRange(nums, 0, length - 2), robRange(nums, 1, length - 1));
};
const robRange = (nums, start, end) => {let first = nums[start], second = Math.max(nums[start], nums[start + 1]);
for (let i = start + 2; i <= end; i++) {
const temp = second;
second = Math.max(first + nums[i], second);
first = temp;
}
return second;
}区别就在与循环导致限度
- 粉刷房子
如果有一排房子，共 n 个，每个房子能够被粉刷成红色、蓝色或者绿色这三种色彩中的一种，你须要粉刷所有的房子并且使其相邻的两个房子色彩不能雷同。
r 17 18 21
b 2 33 10
g 17 7
/**
* @param {number[][]} costs
* @return {number}
*/
var minCost = function(costs) {
let len = costs.length;
if(costs.length == 0) {return 0}
let dp = Array.from(new Array(3), () => {return new Array(len).fill(0);
});
for (let j = 0; j < 3; j++) {dp[j][0] = costs[0][j]
}
for(let i = 1; i < len; i++) {for (let j = 0; j < 3; j++) {let prev1 = dp[(j+2)%3][(i-1)%2];
let prev2 = dp[(j+1)%3][(i-1)%2];
dp[j][i%2] = Math.min(prev1, prev2) + costs[i][j]
}
}
let last = (len-1)%2
return Math.min(dp[0][last], dp[1][last], dp[2][last])
};- 翻转字符
如果一个由 ‘0’ 和 ‘1’ 组成的字符串，是以一些 ‘0’（可能没有 ‘0’）前面跟着一些 ‘1’（也可能没有 ‘1’）的模式组成的，那么该字符串是 枯燥递增 的。
咱们给出一个由字符 ‘0’ 和 ‘1’ 组成的字符串 s，咱们能够将任何 ‘0’ 翻转为 ‘1’ 或者将 ‘1’ 翻转为 ‘0’。
返回使 s 枯燥递增 的最小翻转次数。
利用动静布局解决问题总是从剖析状态转移方程开始的。如果一个只蕴含 ’0’ 和 ’1’ 的字符串 S 的长度为 i +1，它的字符的下标范畴为 0～i。在翻转下标为 i 的字符时假如它的前 i 个字符都曾经依照规定翻转结束，所有的字符 ’0’ 都位于 ’1’ 的后面。
/**
* @param {string} s
* @return {number}
*/
var minFlipsMonoIncr = function(s) {
let len = s.length;
if(len == 0) return 0;
let dp = new Array(2).fill().map(() => {return new Array(len).fill(0);
});
dp[0][0] = s[0] == '0' ? 0 : 1;
dp[1][0] = s[0] == '1' ? 0 : 1;
for(let i = 1; i < len; i++) {let ch = s[i]
let prev0 = dp[0][(i-1)%2]
let prev1 = dp[1][(i-1)%2]
dp[0][i % 2] = prev0 + (ch == '0' ? 0 : 1)
dp[1][i % 2] = Math.min(prev0, prev1) + (ch == '1' ? 0 : 1)
}
return Math.min(dp[0][(len-1) % 2], dp[1][(len-1) % 2])
};- 最长斐波那契数列
题目：输出一个没有反复数字的枯燥递增的数组，数组中至多有 3 个数字，请问数组中最长的斐波那契数列的长度是多少？例如，如果输出的数组是[1，2，3，4，5，6，7，8]，因为其中最长的斐波那契数列是 1、2、3、5、8，因而输入是 5。
/**
* @param {number[]} arr
* @return {number}
*/
var lenLongestFibSubseq = function(arr) {const n = arr.length, map = new Map()
const dp = new Array(n).fill(0).map(() => new Array(n).fill(0))
for(let i = 0; i < n; i++) {map.set(arr[i], i)
}
let ans = 0
for (let i = 1; i < n; i++) {for (let j = 0; j < i; j++) {const k = map.get(arr[i] - arr[j])
dp[i][j] = k >= 0 && k < j ? dp[j][k] + 1 : 2
if (ans < dp[i][j]) ans = dp[i][j]
}
}
return ans > 2 ? ans : 0
};- 起码回文宰割
输出一个字符串，请问至多须要宰割几次才能够使宰割出的每个子字符串都是回文？例如，输出字符串 ”aaba”，至多须要宰割 1 次，从两个相邻字符 ’a’ 两头切一刀将字符串宰割成两个回文子字符串 ”a” 和 ”aba.
/**
* @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];
};构建 dp 数组，常常须要初始化二维数组
new Array(n).fill().map(() => {return new Array(n).fill(false);
});
Array.from(new Array(3), () => {return new Array(3).fill(false);
});双序列（TODO）
- 101 宰割等和子集
function subsetSum(nums, target) {
const n = nums.length + 1;
const dp = new Array(n).fill().map(() => {return new Array(target + 1).fill(false);
});
}- 102 加减的目标值
参考文章
- js 创立二维数组