【算法】动态规划【算法】动态规划

动态规划的基础知识

爬楼梯的最少成本

一个数组 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); }); }