Leetcode 509 题道歉拖更了 2 天，嘿嘿。这周咱们基于动静布局根本思维，做一道 Leetcode 的简略题。 题干简述Leetcode 509 题就是计算斐波那契数列。 公式：F(n) = F(n - 1) + F(n - 2) 给定：n 要求：计算F(n) 解题思路为什么说计算斐波那契数列是动静布局外面最简略的一道题呢？ 是因为题目间接给出了状态转移方程F(n) = F(n - 1) + F(n - 2)，拿着公式计算就能够了。 代码实现class Solution: def fib(self, n: int) -> int: if n == 0: return 0 dp = [0]*(n+1) dp[0] = 0 dp[1] = 1 for i in range(2, n+1): dp[i] = dp[i-1] + dp[i-2] return dp[n]复杂度工夫复杂度O(n)，空间复杂度O(n)。 转载申明：本文章容许转载，原文地址：「动静布局」LeetCode 509(斐波那契数列)
原文归档：「烤冷面讲算法，每周一讲」原文链接：「动静布局」LeetCode 416(宰割等和子集) LeetCode 416上一周讲了01背包问题，这周咱们趁热打铁，用01背包问题的思路来解决 LeetCode 416 题。 题干简述给定：一个只蕴含正整数的非空数组 nums 。 要求：判断 nums 是否能够被宰割成元素和相等的两个子集。 题目详情：416. 宰割等和子集 解题思路解题的关键在于咱们是否从nums中找出一些元素，「元素的和」等于「总和」的一半，如果找失去，答案即为 true，否则就是 false。依据第 1 点，咱们能够把这道题转化为01背包问题，背包容量=nums元素和/2，物品就是nums数组中的每个元素，物品的分量和价值相等，等于元素的值(也就是nums[i])。除此之外还有一些边界条件： 首先，nums中所有元素的和必须为偶数，否则不可能被宰割成元素和相等的两个子整数集。其次，若 nums 中某个元素的值>总元素和/2，间接 return false。图解算法官网案例: Input: nums = [1,5,11,5] Output: true Explanation: The array can be partitioned as [1, 5, 5] and [11]. 就像「01背包问题」这篇文章提到的那样，咱们能够画出这样一个矩阵： 1234567891011nums[0]=111111111111nums[1]=511115666666nums[2]=11111156666611nums[3]=51111566661011代码实现class Solution: def canPartition(self, nums: List[int]) -> bool: s = sum(nums) target = s // 2 # 边界值检测 if s % 2 == 1: return False # 边界值检测 maxNum = 0 for num in (nums): maxNum = max(num, maxNum) if maxNum > target: return False dp = [([0] * target) for p in range(len(nums))] # 填充矩阵第一行 for j in range(0, target): subTarget = j + 1 if subTarget >= nums[0]: dp[0][j] = nums[0] # 填充矩阵残余所有行 for i in range(1, len(nums)): num = nums[i] for j in range(0, target): subTarget = j + 1 if subTarget > num: dp[i][j] = max(dp[i-1][j], dp[i-1][j-num]+num) elif subTarget == num: dp[i][j] = num else: dp[i][j] = dp[i - 1][j] if dp[i][target-1] == target: return True return False复杂度工夫复杂度O(n^2)，空间复杂度O(n^2)，在 LeetCode 下面的体现并不现实： ...
状态机动静布局之股票问题总结前言在后面的三篇股票问题的文章当中咱们一共介绍了6道对于股票相干的算法题，这些算法题的一个集中的特点就是状态比拟多，须要咱们去仔细分析状态之间的转换，而这种状态之间的转换特变像状态机，因而这种动静布局也被称作状态机动静布局。 如果须要认真的去剖析下面思维导图当中的各个问题，能够参考上面的文章： 内容链接交易股票的最佳时机I和II这种动静布局你见过吗——状态机动静布局之股票问题(上)交易股票的最佳时机III和Iv这种动静布局你见过吗——状态机动静布局之股票问题(中)交易股票的最佳时机含冷冻期和手续费这种动静布局你见过吗——状态机动静布局之股票问题(下)本篇文章就是对下面6个问题进行汇总不便大家查阅，如果大家想仔细分析这几个问题还是下面三篇文章更适合，内容更加具体，如果你想疾速理解状态机动静布局，那么这篇文章的状态转移剖析应该可能帮忙你。 在本文谈到的6个问题都是动静布局的问题，因而你能够须要相熟一下动静布局的套路，在求解动静布局问题的时候通常的步骤有以下几个： 寻找可能示意状态的数组dp，即咱们须要寻找dp的含意，剖析须要用几纬数组示意具体的状态。通过剖析问题，寻找动静转移公式。初始化状态数组。通过剖析动静转移方程，确定数组的遍历程序。交易股票的最佳时机I给定一个数组 prices ，它的第 i 个元素 prices[i] 示意一支给定股票第 i 天的价格。你只能抉择 某一天 买入这只股票，并抉择在将来的某一个不同的日子卖出该股票。设计一个算法来计算你所能获取的最大利润。返回你能够从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。状态示意数组在这个问题当中咱们用一个二维数组去示意咱们的状态，在这个问题当中次要有两个状态，一个是手上有股票，另一是手上没有股票： dp[i][0]示意在第i天手上没有股票可能取得的最大的收益，比方咱们在第一天的没有股票的收益为0元。dp[i][1]示意在第i天手上存在股票可能取得的最大的收益，比方咱们在第一天买入股票之后收益为-prices[0]。那么咱们最初的答案是dp[N][0]，这个示意在最初一天，咱们的手中不存在股票，即咱们将股票卖出去可能获取的最大的收益。 状态转移方程当初咱们来剖析一下如何进行状态的转移： dp[i][0]的状态如何从第i-1的状态转移过去： 如果第i-1个状态是手中不存在股票，即dp[i-1][0]，那么第i个状态也没有股票，那么间接是dp[i][0] = dp[i - 1][0]，因为没有进行交易。如果第i-1个状态手中存在股票，即dp[i-1][1]，那么如果想在第i个状态没有股票，那么就须要将股票卖出，那么收益就为dp[i-1][1] +prices[i]，即dp[i][0] = dp[i-1][1] +prices[i]。综合下面的两种转移形式能够失去上面的转移方程：$$dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i])$$ dp[i][1]的状态如何进行转移： 如果第i-1个状态是手中不存在股票，即dp[i-1][0]，而第i个状态有股票，那么dp[i][0] = -prices[i]，因为买入股票，而且只可能买入一次，因而间接等于-prices[i]即可，留神这里不能是dp[i - 1][0] - prices[i]，因为在dp[i-][0]当中可能存在先买入再卖出的状况，而题干要求只能买入卖出一次。如果第i-1个状态手中存在股票，即dp[i-1][1]，而第i个状态有股票，因而不须要进行交易，即dp[i][1]=dp[i - 1][1]。综合下面的两种转移形式能够失去上面的转移方程：$$dp[i][1] = max(dp[i - 1][1], -prices[i]);$$ 参考代码如下： class Solution { public int maxProfit(int[] prices) { int[][] dp = new int[prices.length][2]; // 初始化数组 dp[0][0] 默认等于0 不必 // 显示初始化 dp[0][1] = -prices[0]; for (int i = 1; i < prices.length; i++) { dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]); dp[i][1] = Math.max(dp[i - 1][1], -prices[i]); } return dp[prices.length - 1][0]; }}进行数组空间优化 ...
这种动静布局你见过吗——状态机动静布局之股票问题(下)前言在后面的两篇文章这种动静布局你见过吗——状态机动静布局之股票问题(上)和这种动静布局你见过吗——状态机动静布局之股票问题(中)曾经谈了4道和股票问题相干的题目，具体解释了状态机动静布局和他的基本原理和利用形式。在本篇文章当中，会再介绍剩下的两道股票问题，持续深刻和学习状态机动静布局。 最佳交易股票机会含冷冻期题目给定一个整数数组prices，其中第 prices[i] 示意第 i 天的股票价格 。 设计一个算法计算出最大利润。在满足以下约束条件下，你能够尽可能地实现更多的交易（屡次交易一支股票）:卖出股票后，你无奈在第二天买入股票 (即冷冻期为 1 天)。 留神：你不能同时参加多笔交易（你必须在再次购买前发售掉之前的股票）。 示例示例1: 输出: prices = [1,2,3,0,2]输入: 3 解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]示例2: 输出: prices = [1]输入: 0状态示意数组和状态转移方程和后面的题目一样首先还是须要进行状态的定义和状态转移的剖析，在这个问题当中咱们用一个二维数组dp[i][j]示意各种不同的状态下的收益，在这个问题当中咱们有以下几个状态： dp[i][0]，示意在遍历到第i支股票的时候没有进行一次买入和卖出。 在这个时候没有进行买入和卖出，这个时候的收益和遍历到第i-1支股票的时候没有买入和卖出的状况是一样的，他们的收益都等于0，即dp[i][0] = 0，dp[i - 1][0] = 0。dp[i][1]，示意在遍历到第i支股票的时候手中含有股票，这个状况能够由三种状况转移过去： 在遍历到第i-1支股票的时候手中曾经存在股票了，这个时候只须要放弃状态，那么在第i支股票的时候的收益和第i-1支股票的收益是相等的，即dp[i][1] = dp[i - 1][1]。第二种状况就是在遍历到第i-1支股票的时候手中不存在股票，那么这个时候要想手中存在股票就须要进行买入了，那么就须要破费prices[i]，那么在遍历到第i支股票的时候收益等于dp[i][1] = dp[i - 1][0] - prices[i]。第三种状况是前一天是处于冷冻期（这里所谈到的冷冻期并不只是前2天卖出，导致的前一天的冷冻期，还有可能是更早之前卖出的，而后放弃它的状态，相当于是冷冻期的续期，只不过在续期当中是能够进行买股票的），那么当初是能够进行买入的，即dp[i][1] = dp[i - 1][3] - prices[i]，其中dp[i][3]示意遍历到第i支股票的时候处于冷冻期的收益。综合以上三种状况：$$dp[i][1] = max(dp[i - 1][1], max(dp[i - 1][0] - prices[i], dp[i-1][3] - prices[i]))$$ dp[i][2]，示意在第i支股票的时候手中不含有股票，能够转移到这个状态的状态一共有两种： 在遍历到第i-1支股票的时候手中原本就不含有股票，那么咱们只须要放弃状态即可，即dp[i][2] = dp[i - 1][2]。在遍历到第i-1支股票的时候手中含有股票，那么咱们须要将这个股票进行售出，即dp[i][2] = dp[i - 1][1] + prices[i]。综合以上两种状况：$$dp[i][2] = max(dp[i - 1][2], dp[i - 1][1] + prices[i])$$ ...
前言在后面的文章这种动静布局你见过吗——状态机动静布局之股票问题(上)咱们曾经介绍了两个根本的股票问题，并且对状态机动静布局做出了简要的介绍，以及在状态机当中的状态是如何进行转换的，然而在后面的两个问题当中状态的个数比拟少，可能不不便大家了解状态机的含意，在本篇文章所谈到的两个问题当中状态的数目还是比拟多的，因而对于大家深刻了解状态机动静布局可能会好一点。 卖股票的最佳时机 III题目给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。设计一个算法来计算你所能获取的最大利润。你最多能够实现 两笔 交易。留神：你不能同时参加多笔交易（你必须在再次购买前发售掉之前的股票）。示例示例1 输出：prices = [3,3,5,0,0,3,1,4] 输入：6 解释：在第 4 天（股票价格 = 0）的时候买入，在第 6 天（股票价格 = 3）的时候卖出，这笔交易所能取得利润 = 3-0 = 3 。随后，在第 7 天（股票价格 = 1）的时候买入，在第 8 天 （股票价格 = 4）的时候卖出，这笔交易所能取得利润 = 4-1 = 3 。 示例2 输出：prices = [1,2,3,4,5] 输入：4 解释：在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能取得利润 = 5-1 = 4 。留神你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。因为这样属于同时参加了多笔交易，你必须在再次购买前发售掉之前的股票。 这道题目跟之前的两道题目不同之处在于，在上篇文章当中的两道题要么是可能购买一次，要么可能购买无数次，而在本道题目当中只可能购买两次，在这种状况下咱们应该如何定义各种状态呢？ 状态示意数组和状态转移在这道题目当中咱们也是二维数组进行状态的示意，二维数组为dp[N][5]，5示意咱们有5个状态，dp[N][i]示意第N天的第i个状态可能多大的收益！（为了不便上面介绍，假如一天有一个股票，dp[N][]示意第N天的状态，对应第N个股票的状态） dp[N][0]，示意第N天一次买入和卖出的操作都没有过，那么dp[N][0] = dp[N - 1][0]，跟前一天的状态一样，都没有进行股票的买入和卖出，其实也能够间接令dp[N][0] = 0，因为没有进行操作咱们的收益必定等于0。dp[N][1]，示意第N天曾经进行过第一次买入，这个买入能够是在第N天进行买入，也能够在后面N-1天买入，而后在第N天放弃状态。 ...
前言在本篇文章当中次要通过介绍各种股票问题跟大家介绍状态机动静布局，次要理解在股票问题当中是如何在动静布局当中进行状态转移的，通过认真分析状态转移过程给大家介绍状态机动静布局。所谓状态机，就是有很多状态和他们之间的转移关系组成起来造成零碎，这个说法看起来有点高大上，其实很简略，在前面讲动静布局解法的时候大家就明确了。 交易股票的最佳时机I给定一个数组 prices ，它的第 i 个元素 prices[i] 示意一支给定股票第 i 天的价格。你只能抉择 某一天 买入这只股票，并抉择在将来的某一个不同的日子卖出该股票。设计一个算法来计算你所能获取的最大利润。返回你能够从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。 示例 1： 输出：[7,1,5,3,6,4] 输入：5 解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。留神利润不能是 7-1 = 6, 因为卖出价格须要大于买入价格；同时，你不能在买入前卖出股票。 示例 2： 输出：prices = [7,6,4,3,1] 输入：0 解释：在这种状况下, 没有交易实现, 所以最大利润为 0。 暴力解法在这个问题当中，咱们的工作是在某一天买入股票，而后在将来某天再将股票卖出去，那么咱们就能够用一个二重循环，第一层循环遍历每一天的股票，第二层循环遍历该天之后的股票，而后找到差值最大的那一天即可，也就是寻找某天前面价值最高的股票！通过做差失去差值，将差值最大的返回即可！ class Solution { public int maxProfit(int[] prices){ int ans = 0; for (int i = 0; i < prices.length - 1; i++) { for (int j = i + 1; j < prices.length; j++) { ans = Math.max(ans, prices[j] - prices[i]); } } return ans; }}下面的代码的工夫复杂度为$O(n^2)$，空间复杂度为$O(1)$，因为工夫简单度过高，下面的代码在Leetcode下面提交会超时。 ...
装满背包的递推公式 dp[j] += dp[j - nums[i]];dp[j]的含意是指在背包容量为j的状况下，背包能装的最大分量nums[i]就是第i个物品的分量 动静布局就是以后值依赖于前一个值，实现全局最优 备忘：如果求组合数，外层遍历物品如果求排列数，外层遍历背包 如果遍历整颗树，递归函数就不能有返回值遍历某一条固定路线，递归函数就肯定要有返回值 二叉树节点的深度：指从根节点到该节点的最长简略门路边的条数二叉树节点的高度：指从该节点到叶子节点的最长简略门路边的条数 6.24算法题
动静布局的基础知识爬楼梯的起码老本一个数组 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];};单序列问题单序列问题是与动静布局相干的问题中最有可能在算法面试中遇到的题型。这类题目都有适宜使用动静布局的问题的特点，如解决问题须要若干步骤，并且每个步骤都面临若干抉择，须要计算解的数目或最优解。除此之外，这类题目的输出通常是一个序列，如一个一维数组或字符串。 ...
背包问题的外围公式把每个背包问题的外围代码放在一块，更好的辨别不同问题的代码实现。当然，在实现代码之前，要先理解每个背包问题解决问题的思路。 物品的分量数组是 weight (int[])，价值数组是 value (int[])，背包容量是 bagWeight 1. 0-1 背包从大到小遍历，为了保障每个物品仅被增加一次 1.1 应用二维数组存储递推公式 dp[i][j] = max(dp[i-1][j], dp[i-1][j - weight[i]] + value[i]) (dp[i][j]：放入物品和不放入物品，哪个值大) dp 大小 int[weight.size()][bagWeight+1] （[物品个数][背包容量+1]） 代码 // 先遍历物品，再遍历背包for(int i = 0; i < weight.size(); i++) { for(int j = bagWeight; j >= 0; j--) { if (j < weight[i]) dp[i][j] = dp[i-1][j] else dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight[i]] + value[i]) }}1.2 应用一维数组存储递推公式 dp[j] = max(dp[j], dp[j - weight[i]] + value[i])( dp[j]：放入物品和不放入物品，哪个值大) ...
分割咱们：有道技术团队助手：ydtech01 / 邮箱：[ydtech@rd.netease.com] 之前学习基础知识的时候也说了，递推和动静布局有这暧昧不清的关系，能够说，动静布局就是多了一个决策过程的递推。因而，咱们明天的刷题也会波及到一些比较简单的动静布局的题目，同样可能对咱们粗浅的了解递推算法起到帮忙，也为咱们之后深刻学习动静布局算法和动静布局的优化打下基础。 一、前置常识每一个递推算法，都有一个递推公式，通过递推公式咱们能够更加明确的理解递推算法。 1.1 斐波那契数列的递推公式应用场景：当咱们下（上）一行的状态能够仅仅通过上（下）一行的信息推导进去，并要求咱们求解最初（第）一行时，咱们无需将每一行的数据都存储在数组当中，能够通过滚动数组的技巧，节俭空间复杂度。 具体实现：假如咱们曾经晓得第一行的数据，并且通过第一行数据通过肯定的运算能够失去第二行的数据，那么，咱们只须要一个数组长期存储两行数据，就能够将之后的每一行数据的后果计算出来，一直的滚动替换这两行数据，最终求解出最初一行数据的形式。关键点：推导计算以后行和下（上）一行的索引。因为数组是滚动的，因而，咱们指标行的索引也是随时变动的，以下为求取以后行和上（下）一行的通用公式： 以后行： const curIdx = i % 2因为咱们的滚动数组只有2行，因而，以后索引只有与2求模即可；上（下）一行：const preIdx = +!curIdx因为滚动数组只有两行，索引要么是0，要么是1，咱们对以后行取反便可失去上（下）一行的索引（留神，在js中，对1取反是false,对0取反是true,因而咱们通过一个隐式类型转换将布尔类型转换为数字类型）。这道题咱们要怎么了解呢？咱们如果想要爬到第 n 阶楼梯，那么上一步有可能是在 n-1 ,也有可能是在 n-2 理论应用：前面刷题时会常常用到，详见下文 二、刷题正餐2.1 LeetCode 120. 三角形最小门路和2.1.1 解题思路依照咱们之前将的递推套路：1. 定义递推状态：在这道题中，咱们每走一步的门路和次要取决于以后所处的行数i和以后的列数j，因而，咱们这道题的递推状态应该是：dp[i, j]2. 递推公式：确定了递推状态之后，咱们就要确定递推公式了。那么，第i行第j列的数据要如何能力推导进去呢？首先，根据题意，咱们要求最小门路和，如果咱们从最底下往上走，那么咱们能够晓得，下一行i的数据应该是上一行i+1非法门路的最小值加上以后走到节点的值。因而，咱们失去了如下公式： // 第i行第j列数据的推导公式dp[i, j] = min(dp[i+1, j], dp[i+1, j+1]) + val[i,j]3.剖析边界条件：咱们须要将咱们题目已知的条件初始化到咱们的递推数组当中作为边界条件。这道题中，边界条件就是最初一行的数据，咱们将最初一行的数据先退出到滚动数组当中，这样之后就能够依据最初一行数据一直的往上推导总门路和，从而找到最小门路。4. 程序实现：咱们间接应用循环加滚动数组技巧实现。 2.1.2 代码演示function minimumTotal(triangle: number[][]): number { const n = triangle.length; // 递推公式（状态本义方程）以下为自底向上走的公式 // dp[i, j] = min(dp[i+1, j], dp[i+1, j+1]) + val[i,j] // 因为i只跟i+1无关，因而，咱们能够用滚动数组的技巧定义dp数组 let dp: number[][] = []; for(let i=0;i<2;i++){ dp.push([]); } // 首先初始化最初一行的数值，因为应用了滚动数组的技巧，因而，咱们最初一行的索引应该是(n-1)%2 for(let i=0;i<n;i++) { dp[(n-1)%2][i] = triangle[n-1][i]; } // 而后从倒数第二行开始求值 for(let i = n-2;i>=0;--i) { // 因为应用了滚动数组，因而，以后行的下标为i%2,而下一行的下标则是以后行下标取反 let idx = i % 2; let nextIdx = +!idx; // 依据下面的公式计算出每一个地位上的值 for (let j=0; j <= i; j++) { dp[idx][j] = Math.min(dp[nextIdx][j], dp[nextIdx][j + 1]) + triangle[i][j]; } } // 最终，三角形顶点的那个值就是咱们要求的值 return dp[0][0];};2.2 LeetCode 119. 杨辉三角 II2.2.1 解题思路这道题与上一道题相似，仍然能够依据上一行推导出下一行的值，因而还是要祭出滚动数组的技巧，递推状态与递推公式的剖析也比拟相似，大家能够本人尝试推导。而这一道题的边界条件，其实就是每一行的第一位都应该是1。 ...
问题：有两个字符串str和str2，求出两个字符串中最长公共子串长度。 比方：str=acbcbcef，str2=abcbced，则str和str2的最长公共子串为bcbce，最长公共子串长度为5。 计划：如果字符雷同则置为1，否则置为0缩小反复计算，arr[i] [j] = arr[i-1] [j-1]，此处要留神的点是当i==0 || j==0时要间接设值。 Java代码实现： // 动静布局实现，工夫复杂度O(m*n),空间复杂度(m*n) private static String getLcs(String s1, String s2) { int maxLen = 0, maxEnd = 0; int[][] arr = new int[s1.length()][s2.length()]; for (int i = 0; i < s1.length(); i++) { for (int j = 0; j < s2.length(); j++) { if (s1.charAt(i) == s2.charAt(j)) { if (i == 0 || j == 0) { arr[i][j] = 1; } else { arr[i][j] = arr[i - 1][j - 1] + 1; } } else { arr[i][j] = 0; } if (arr[i][j] > maxLen) { maxEnd = i; maxLen = arr[i][j]; } } } if (maxLen == 0) { return ""; } return s1.substring(maxEnd - maxLen + 1, maxEnd); }参考文章 求两个字符串的最长公共子串https://blog.csdn.net/qq_2580... ...
摘要：平时练习算法题学习算法常识时，常常会发现题解里写着“动静布局”，外面一上来就是一个简单的dp公式，对于新人来说除了说声“妙啊”，剩下就是纳闷，他是怎么想到这个公式的？我能想到吗？这玩意工作中有用吗？本文分享自华为云社区《动静布局到底是怎么想到的？【奔跑吧！JAVA】》，原文作者：breakDraw。 平时练习算法题学习算法常识时，常常会发现题解里写着“动静布局”，外面一上来就是一个简单的dp公式，对于新人来说除了说声 剩下就是纳闷，他是怎么想到这个公式的？我能想到吗？这玩意工作中有用吗？加上“动静布局”这高端的名字，而后就劝退了不少试图去了解他的人。 动静布局听起来太吓人，能够换个说法我在心田更喜爱叫他“状态缓存”如果是服务开发，置信很相熟这个词语， 利用缓存来放慢一些反复的申请的响应速度。而这个缓存的特点是 和其余缓存有所关联。 比方咱们的服务要计算7天内的某金钱总和，计算后要缓存一下。起初又收到一个申请，要计算8天内的金钱总和那咱们只须要取之前算过的7天内的金钱综合，加上第8天的金钱就行了。 1+4的思考套路本人针对动静布局总结了一个本人的思考套路，我叫他1组例子4个问题，就叫1+4好了，通过这5个过程，能够站在普通人的角度（就是非acm大佬那种的角度），去了解动静布局是如何被思考进去的 在超时的思路上写出一组计算过程的例子在超时例子的根底上，有哪些反复、节约的中央？如何定义dp数组状态的变动方向是什么，是怎么变动的边界状态是什么简略例子以一道简略题为例：爬楼梯：https://leetcode-cn.com/problems/climbing-stairs/ 这时候就要静下心，察看这个解法的例子中是否有反复经验的场景，而这个反复经验的场景就叫状态。我解决动静布局的题目时， 都会问本人3个问题，个别就能顺利地解决。 ①在超时的思路上写出一组计算过程的例子如果咱们思考最简略的解法， 就是从终点开始，每次抉择走1步或者走2步，看下是否走到起点，能走到则办法数+1。但这种办法注定超时（O（n^2)）但我还是照着这个过程模仿了一下，轻易列了几个1 ->2-> 3-> 4-> 51 ->2 ->3-> 51->3->4->51->3->5 ②在超时例子的根底上，有哪些反复、节约的中央？在下面，我发现了反复的中央 也就是说从3到5总共就2种路线，曾经在1->2之后计算过了，我前面从1走到3再往后走时，没必要再去算了。换言之，当我走到3的时候，其实早就能够晓得前面还剩下多少种走法。发现反复的中央后，就能够开始建设dp公式了。 ③如何定义dp数组？定义dp数组，也就是定义下面提到的反复的中央。从新看下之前的那句话当我走到3的时候，其实早就能够晓得前面还剩下多少种走法。所以dp[3]代表的就是从3往后，有多少种可走的办法。 ④状态的变动方向是什么，是怎么变动的首先思考状态的变动方向从新看这句话：当我走到3的时候，其实早就能够晓得前面还剩下多少种走法 阐明后果取决于往 前面 的状态因而咱们要先计算前面的状态, 即从后往前算 接着思考这个前面的状态和以后的状态有什么分割，是怎么变动的这个个别都蕴含在题目条件中依据题意，要么走2步，要么走1步，因而每当我走到一层时，下一次就2种状态能够变动。那么对于第3层而言，他后续有2种走法，走1步或者走2步那么他的状况就是dp[3] = dp[3+1] + dp{3+2}如果层数设为i，那么这个变动状况就是dp[i] = dp[i+1] + dp[i+2] ⑤边界状态是什么？边界状态就是不须要依赖前面的状态了，间接能够失去后果的状态。在这里必定就是最初一层dp[n]， 最初一层默认是一种走法。 dp[n]=1 实现依据下面的过程，本人便定义了这个状态和变动 定义：dp[i] : 代表从第i层往后，有多少种走法方向和变动：dp[i] = dp[i+1] + dp[i+2];边界: dp[n] = 1依据这个写代码就很容易了代码： public int climbStairs(int n) { int[] dp = new int[n + 1]; dp[n] = 1; dp[n-1] = 1; for(int i = n-2; i >=0;i--) { dp[i] = dp[i+1] + dp[i+2]; } return dp[0]; }进阶版，二维的动静布局https://leetcode-cn.com/problems/number-of-ways-to-stay-in-the-same-place-after-some-steps/ ...
动静布局的外围是当时找到该事件的动静转移方程，我临时只学习了几个经典的dp案例，道阻且长！ Bone CollectorMany years ago , in Teddy’s hometown there was a man who was called “Bone Collector”. This man like to collect varies of bones , such as dog’s , cow’s , also he went to the grave …The bone collector had a big bag with a volume of V ,and along his trip of collecting there are a lot of bones , obviously , different bone has different value and different volume, now given the each bone’s value along his trip , can you calculate out the maximum of the total value the bone collector can get ? ...
有 NN 件物品和一个容量是 VV 的背包。每件物品只能应用一次。 第 ii 件物品的体积是 vivi，价值是 wiwi。 求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。输入最大价值。 输出格局第一行两个整数，N，VN，V，用空格隔开，别离示意物品数量和背包容积。 接下来有 NN 行，每行两个整数 vi,wivi,wi，用空格隔开，别离示意第 ii 件物品的体积和价值。 输入格局输入一个整数，示意最大价值。 数据范畴0<N,V≤10000<N,V≤10000<vi,wi≤10000<vi,wi≤1000 输出样例4 51 22 43 44 5 输入样例：8
题目地址（464. 我能赢么）https://leetcode-cn.com/probl... 题目形容在 "100 game" 这个游戏中，两名玩家轮流抉择从 1 到 10 的任意整数，累计整数和，先使得累计整数和达到或超过 100 的玩家，即为胜者。如果咱们将游戏规则改为 “玩家不能重复使用整数” 呢？例如，两个玩家能够轮流从公共整数池中抽取从 1 到 15 的整数（不放回），直到累计整数和 >= 100。给定一个整数 maxChoosableInteger （整数池中可抉择的最大数）和另一个整数 desiredTotal（累计和），判断先出手的玩家是否能稳赢（假如两位玩家游戏时都体现最佳）？你能够假如 maxChoosableInteger 不会大于 20， desiredTotal 不会大于 300。示例：输出：maxChoosableInteger = 10desiredTotal = 11输入：false解释：无论第一个玩家抉择哪个整数，他都会失败。第一个玩家能够抉择从 1 到 10 的整数。如果第一个玩家抉择 1，那么第二个玩家只能抉择从 2 到 10 的整数。第二个玩家能够通过抉择整数 10（那么累积和为 11 >= desiredTotal），从而取得胜利.同样地，第一个玩家抉择任意其余整数，第二个玩家都会赢。前置常识动静布局回溯公司阿里linkedin暴力解（超时）思路题目的函数签名如下： def canIWin(self, maxChoosableInteger: int, desiredTotal: int) -> bool:即给你两个整数 maxChoosableInteger 和 desiredTotal，让你返回一个布尔值。 两种非凡状况首先思考两种非凡状况，前面所有的解法这两种非凡状况都实用，因而不再赘述。 如果 desiredTotal 是小于等于 maxChoosableInteger 的，间接返回 True，这不难理解。如果 [1, maxChoosableInteger] 全副数字之和小于 desiredTotal，谁都无奈赢，返回 False。个别状况思考完了非凡状况，咱们持续思考个别状况。 首先咱们来简化一下问题， 如果数字能够轻易选呢？这个问题就简略多了，和爬楼梯没啥区别。这里思考暴力求解，应用 DFS + 模仿的形式来解决。 ...
题目地址（面试题 17.23. 最大黑方阵）https://leetcode-cn.com/probl... 题目形容给定一个方阵，其中每个单元(像素)非黑即白。设计一个算法，找出 4 条边皆为彩色像素的最大子方阵。返回一个数组 [r, c, size] ，其中 r, c 别离代表子方阵左上角的行号和列号，size 是子方阵的边长。若有多个满足条件的子方阵，返回 r 最小的，若 r 雷同，返回 c 最小的子方阵。若无满足条件的子方阵，返回空数组。示例 1:输出:[ [1,0,1], [0,0,1], [0,0,1]]输入: [1,0,2]解释: 输出中 0 代表彩色，1 代表红色，标粗的元素即为满足条件的最大子方阵示例 2:输出:[ [0,1,1], [1,0,1], [1,1,0]]输入: [0,0,1]提醒：matrix.length == matrix[0].length <= 200前置常识动静布局公司暂无思路看了下数据范畴，矩阵大小不超过 $200 \times 200$，因而答案应该就是暴力，这个数据范畴差不多 N 的三次方的复杂度都能够通过，其中 N 为矩阵的边长。起因我也在之前的文章来和大家聊聊我是如何刷题的（第三弹）中讲过了，那就是 $200^3$ 刚好是是 800 万，再多就很容易超过 1000 万了。 乍一看，这道题和 221. 最大正方形，实则不然。 这道题是能够空心的，只有边长是局部都是 0 即可，这就齐全不同了。 如下图，红色局部就是答案。只须要保障边全副是 0 就好了，所以外面有一个 1 无所谓的。 咱们无妨从部分动手，看能不能关上思路。 这是一种罕用的技巧，当你面对难题无从下手的时候能够画个图，从非凡状况和部分状况开始，帮忙咱们关上思路。比方我想计算以如下图红色格子为右下角的最大黑方阵。咱们能够从以后点向上向左扩大直到非 0。 在下面的例子中，不难看出其最大黑方阵不会超过 min(4, 5)。 ...
动静布局算法 问题要害特色：最优子结构，子问题重叠 确定定义问题规模解的个别递归表达式对问题规模升序遍历每种规模的问题应用递归表达式, 其中递归求解子问题间接通过拜访mem获取计算完以后规模问题后, 向mem中存入后果
最近老是想起陈芝麻烂谷子的事件，阐明工龄所剩无几了。 - 1 -又是在那边远的 2009 年，那个“杯具”曾经不是杯具的年头，度厂办个算法较量，办出了点儿杯具的滋味。 较量的名字叫“百度之星”，那些年在校园里影响力还蛮大的（如同当初还是），大略赛制就是通过初赛、复赛、决赛这么几轮，选出几个社会主义四有青年瓜分奖金。值得一提的是，头两年（05、06）冠军都被楼教主承包了。 为什么说有点杯具的滋味呢，因为那年的初赛完结当前，度厂搞了个骚操作，把所有参赛选手提交的代码导出来，打了个包，发在贴吧里。 于是贴吧忽然就炸了。 - 2 -要晓得初赛是网络赛，各个学校的 ACM（或OI） 集训队的队员们很可能都是凑在机房一起参加，毕竟毛主席教诲咱们人多力量大嘛。 所以这就有点意思了：如果同一个题，两份代码长得很像，阐明相互剽窃概率就很大。 问题是参赛人数有点多，两两比照这 O(n^2) 的工夫复杂度，靠人肉有点儿吃不消；但这么大一个瓜，光看不吃又有点惋惜了。 那么这瓜到底该怎么吃呢？ - 3 -还好，作为一个比赛战五渣的我，通过初赛的能力没有，搞事件的能力还是有一点的。 为了比照两份代码的类似度，那我首先得找到一个指标。 作为一个长于 舞弊 思考的社会主义三无青年，我预计作弊者在拿到弊友代码后不会间接提交，至多会做些更换变量名之类操作；但比赛工夫紧迫，大概率来不及批改整体框架。 那么，只有我能算出批改的水平，就能判断类似度了：假如两份代码长度别离是 m、n，批改了 x 个字符， 咱们大抵能够把 100% - x / ((m + n) / 2) 当成类似度（没被批改的字符占比）。 但如何计算这批改的水平呢？毕竟批改前后代码长度很可能不同，不适宜通过逐字比拟来找到差异。 - 4 -既然间接解决两段代码有点辣手，那无妨先考虑一下简略的 case 。 比如说要将字符串 "a" 改成 "b"，这个简略，只有改一个字符就行。 又比如说要将字符串 "a" 改成 "ab"，这个也简略，只有增加一个字符就行。 再比如说要将字符串 "ab" 改成 "b"，这个仍然简略，只有删除一个字符就行。 如果我能算出将一段字符串通过增加、删除、批改三种操作批改成另一个字符串的起码操作次数，应该就能把这瓜给吃了。 如同是找到了方向，然而要怎么实现呢？ - 5 -既然间接解决两段代码还是有点辣手，那无妨再考虑一下略微简单一点的 case ，比方把字符串 X = "baidu" 变成 Y = "bytedance"。 ...
前言在leetcode上做题时，经常会碰到有关动态规划的问题，在leetcode的题库界面可以看到有着动态规划标签的题目还是挺多的，为了搞明白这个东东，我查了不少资料，现在来整理一下思路，试试把动态规划这个概念讲清楚。 引用段维基动态规划（英语：Dynamic programming，简称DP）是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。动态规划常常适用于有重叠子问题[1]和最优子结构性质的问题，动态规划方法所耗时间往往远少于朴素解法。动态规划背后的基本思想非常简单。大致上，若要解一个给定问题，我们需要解其不同部分（即子问题），再根据子问题的解以得出原问题的解。通常许多子问题非常相似，为此动态规划法试图仅仅解决每个子问题一次，从而减少计算量：一旦某个给定子问题的解已经算出，则将其记忆化存储，以便下次需要同一个子问题解之时直接查表。这种做法在重复子问题的数目关于输入的规模呈指数增长时特别有用。——来自维基百科这里的定义好像术语有点过多，我觉得最重要的就是那句“把原问题分解为相对简单的子问题的方式求解复杂问题”。动态规划将一个复杂的大问题分解成小问题，拆解问题，就是动态规划的核心。 来举个栗子来看一道经典题目： 假设你正在爬楼梯，楼梯有n级台阶，你每次只能一级或两级楼梯，请问你一共有多少种方式爬完？现在我们来试着解决这个问题：1.递归解决先假设我们只爬五级楼梯，如果直接暴力枚举似乎有点麻烦，我们可以想一下，在你将要爬完的时候，也就是在爬到第五级之前，其实只有两种情况，一种在第三级，一种在第四级。我们最终的解是爬完五级的全部走法，记为f(5)，那么假设爬三层总走法是f(3)，四层总数是f(4)，思考一下，爬完五层的走法总数是不是f(5)=f(3)+f(4)呢？从第三级到第五级，爬两级，从第四到第五，爬一级。那么爬三级的走法加上爬四级的走法，刚好就是爬五级的走法总数。这样推算下来，只要我们有爬一级和爬两级的情况，就可以用递归求f(n)=f(n-1)+f(n-2)了。爬一级就走一步，一种走法，爬两级，要么走两次一步，要么直接两级台阶一步到位，两种走法。代码实现： def climbStairs(n): if n < 1: return 0 if n == 1: return 1 if n == 2: return 2 return climbStairs(n-1) + climbStairs(n-2)看上去没什么问题，让我们来看一下时间复杂度。从这个图里可以看到直接使用递归是有重复计算的，并且当n越大，也就是楼梯级数越多，重复计算的量就越大，这是我们不可忍受的。时间复杂度：O(2n)空间复杂度：O(n) 2.自顶向下备忘录既然有重复计算，那么我们把已经计算过的值用哈希表缓存起来，不就能提高效率了吗？代码实现： memo = {}def climbStairs(n): if n in memo: return memo[n] if n < 1: return 0 if n == 1 or n == 2: return n else: memo[n] = climbStairs(n-1) + climbStairs(n-2) return memo[n]所有计算过的值都存储在memo这个字典里，如果结果已经在字典中，我们就不需要再重复计算了。与前一个方法时间对比，把两个函数名改一下，使用time.time()方法来算一下执行时间： if __name__ == '__main__': start = time.time() print(climbStairs1(35)) print("递归耗时{:.8f} second".format(time.time()-start)) start = time.time() memo = {} print(climbStairs2(35)) print("备忘录耗时{:.8f} second".format(time.time()-start)) # 结果14930352递归耗时6.11950040 second14930352备忘录耗时0.00399756 second>>> 可以看到速度有很明显的提示。时间复杂度：O(n)空间复杂度：O(n) ...
陌上人如玉公子世无双 前言n个台阶 一次只能走 一步或者两步，问有多少种走法 问题分析假设有n个台阶： 当 n=0，即没有台阶时 走法为0 当 n=1，台阶为1时 走法为1 当 n=2，台阶为2时 走法为2：一步一步 ， 两步 当为n个时, 相当于在n-1这个台阶走一步或者在n-2这个台阶走两步 所以n个台阶 相当于 n-1个台阶的走法加上n-2个台阶的走法 递归实现： 递归函数： dp(n) = dp(n-1) + dp(n-2) 递归出口： n=0 return 0 n=1 return 1 n=2 return 2 如果有对递归思想不是很懂的可以查看我之前发过的递归文章链接描述，相信对你有很大帮助 代码实现/** n个台阶 一次只能走 一步l或者两步，问有多少步解法 当 n=0，即没有台阶时 走法为0 当 n=1，台阶为1时 走法为1 当 n=2，台阶为2时 走法为：一步一步 ， 两步 当为n个时, 相当于在n-1这个台阶走一步或者在n-2这个台阶走两步 所以n个台阶 相当于 n-1个台阶的走法加上n-2个台阶的走法 递归实现： 递归函数： dp(n) = dp(n-1) + dp(n-2) 递归出口： n=0 return 0、n=1 return 1、n=2 return 2 @param n 个台阶 @return n个台阶走法 */ int dp(int n) { if (n == 0) { return 0; } else if (n == 1) { return 1; } else if (n == 2) { return 2; } else { return dp(n-1) + dp(n-2); } }功能测试 int main(int argc, const char * argv[]) { @autoreleasepool { int sum; sum = dp(2); NSLog(@"2个台阶的走法：%d\n", sum); sum = dp(3); NSLog(@"3个台阶的走法：%d\n", sum); sum = dp(4); NSLog(@"4个台阶的走法：%d\n", sum); sum = dp(9); NSLog(@"9个台阶的走法：%d\n", sum); } return 0; } ...
求无向图中任意两点之间最短距离 使用Floyd算法实现。Floyd算法是动态规划思想的一种体现，既然用到动态规划，那么就需要找到状态转移方程。在本例中，假设求1->2之间的最短距离，很容易得到f(2) = min{f(3)+1,f(5)+1}推出转移方程就是 f(d) = min(f(0)>0->f(0)+1...f(d-1)>0->f(d-1)+1) JAVA编码实现 public static void main(String[] args) { int[][] maps = { {0, 0, 0, 0, 0, 0}, {0, 0, 0, 1, 1, 0}, {0, 0, 0, 1, 0, 1}, {0, 1, 1, 0, 0, 1}, {0, 1, 0, 0, 0, 1}, {0, 0, 1, 1, 1, 0} }; int shortDistance = shortDistance(maps, 1, 2); System.out.println("最短路径:" + shortDistance); } public static int shortDistance(int[][] maps, int x, int y) { int min = maps[x][y]; if (min == 0) { for (int i = 1; i < maps[y].length; i++) { if (maps[x][i] == 1) { int tmp = shortDistance(maps, x, i); if (tmp + 1 < min || min == 0) { min = tmp + 1; } } } } return min; }
原作者：金子冴校阅：内野良一翻译：叶子原文链接目录什么是动态规划(Dynamic Programming)例题：用Dijkstra的方法解决最短路径问题(Python实现)使用动态规划解决问题的步骤参考什么是动态规划(Dynamic Programming)动态规划概要动态规划是一种解题手法的总称。它通过将一个无法解决的大问题分解成复数个小问题(也叫子问题)，然后在解决这些小问题的基础之上来解决原始的大问题。通过使用动态规划，我们能将一部分在多项式时间内无法解决的问题，在类似多项式的时间内求得最优解(稍后会进行说明)。判断一个问题是否可以通过动态规划来解决的时，我们需要判断该问题是否满足可分治(分而治之)和可记忆(将阶段性成果进行缓存，便于重复利用)两个条件。首先，让我们先去理解:多项式时间、分而治之、以及记忆化(Memoization)。 什么是多项式时间，什么是多项式时间算法多项式时间是指由多项式表示的计算时间。多项式时间算法是指当入力的大小(长度或者个数)是n的时候，计算时间(执行步数)的上限在n的多项式时间内能够表示的算法。比如，计算九九乘法表的算法的计算时间可以表示为9x9。将其扩展到nxn的时候，计算时间用大O记法来表示的话，可以表示为O(n2)。这表明该算法的计算时间的上限可以用n2来表示，因此计算nxn的乘法的算法可以说是多项式算法。但是，在多项式时间内无法解决的问题也是存在的，比如说接下来将要说明的最短路径问题，在多项式时间内就无法解决。如下图所示的加权路线图，找一个从START开始到到达GOAL的花费最短(权重最小)的路线。 为了求最短路线，我们需要考虑全部路线的排列组合，在此基础之上进行花费的计算，要使得花费最小，那就需要找到最短的路径。像这样的问题，入力的规模每增大一点，路线的组合就呈指数级增加，因此计算全部路线的花费是不现实的。但是，如果使用了动态规划，就可以求得类似最短路径这样的在多项式时间内无法解决的问题的最优解。计算时会使用分而治之和记忆化两种手法。 什么是分而治之(分治)分治指的是将目标问题分割成复数个子问题的手法。让我们试着将刚才提到的最短路径问题进行子问题分解。对于刚才提到的例子，首先不要去考虑从START开始能够到达END的所有路线，而应该只考虑在某个时间点能够推进的路线。所以对于最开始的路线，只需要考虑START到a，b，c，d这四条。考虑到我们要解决的是最短路径的问题，这里我们选择从START开始花费最小的START->b路线开始。接着，我们只需考虑从b点出发能够推进的路线，这里我们也是选择花费最少的路线，b->g路线。 像这样，将一个需要考虑全部路径的问题转换为只考虑某个时间点能够推进的路线的问题(子问题)的分治手法，叫做分而治之。 什么是记忆化记忆化是指将计算结果保存到内存上，之后再次利用的手法。作为解释记忆化的例子，让我们来思考一下斐波那契数列的问题。这里我们省略斐波那契数列数列的说明。使用python进行斐波那契数列计算的场合，代码编写如下所示： 清单1 CulcFibonacci.py import sys# フィボナッチ数の計算def culc_fibonacci(n): if n > 1: return culc_fibonacci(n-1) + culc_fibonacci(n-2) elif n == 1: return 1 else: return 0def main(): # 1～10番目フィボナッチ数列を表示 # ⇒ 0, 1, 1, 2, 3, 5, 8, 13, 21, 34 for n in range(10): fibonacci_n = culc_fibonacci(n) print(fibonacci_n, end='') if not n == 9: print(', ', end='')if __name__ == '__main__': main() sys.exit(0)但是，清单1所示代码，在计算n=10的时候，必须去计算n=9～1，因此计算时间是O(n:的n次幂)(:实数)，所以当n变大的时候，相关的计算量会呈指数级增长。下图表示的是斐波那契数列的计算过程。从下图我们可以看出，除了f(10)之外的所有计算都不止一次。 ...
题目给定一个三角形，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。 例如，给定三角形： [ [2], [3,4], [6,5,7], [4,1,8,3]]自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。 说明： 如果你可以只使用 O(n) 的额外空间（n 为三角形的总行数）来解决这个问题，那么你的算法会很加分。 题解这道题目和之前A过的杨辉三角差不多,一看就是动态规划。动态规划最主要的是确定状态表达式。而要求在o(n)的空间复杂度来解决这个问题，最主要的是要想清楚，更新状态的时候，不破坏下一次计算需要用到的状态。我们采用"bottom-up"的动态规划方法来解本题。 状态表达式为：dp[j] = min(dp[j], dp[j+1]) + triangle[j]; class Solution { public int minimumTotal(List<List<Integer>> triangle) { int row = triangle.size(); List<Integer> res = new LinkedList<>(triangle.get(row - 1)); for (int i = row - 2; i >= 0; i--) { List<Integer> currentRow = triangle.get(i); for (int j = 0; j < currentRow.size(); j++) { res.set(j, Math.min(res.get(j), res.get(j + 1)) + currentRow.get(j)); } } return res.get(0); }}热门阅读百度社招面试题——Redis实现分布式锁【Leetcode】114. 二叉树展开为链表社招面试总结——算法题篇Redis中的集合类型是怎么实现的？ ...
动态规划维基百科对动态规划（Dynamic programming，简称DP）的定义是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。斐波那契数列斐波那契数列是一个典型的可以把原问题分解为相对简单的子问题的方式求解复杂问题的例子。下面是斐波那契数列的数学定义:F(0)=0，F(1)=1F(2)=F(1)+F(0)=1+0=1F(n)=F(n-1)+F(n-2) (n>=2)根据这个数学定义，我们可以用递归的方式很轻松的实现这个算法。package mainimport ( “fmt” “time”)func fib(n int) int { if n <= 1 { return n } return fib(n-1) + fib(n-2)}func main() { start := time.Now().Unix() fib(45) end := time.Now().Unix() fmt.Println(end-start)}上面代码我们求的是F(45)，代码非常的简单，但发现计算时间达到了6秒左右，效率十分低下，下面是根据刚刚的代码画出的一个F(5)的树状图：从图中可以看出F(3)计算了2次，F(2)计算了3次，F(1)计算了4次，发生了很多重复计算，这也是造成效率低下的原因，要优化的思路就是去除掉这些不必要的重复计算。现在我们将每个子问题的计算结果存储起来，当再次碰到同一个子问题时，就可以直接从之前存储的结果中取值，就不用再次计算了。比如第一次碰到计算F(2)时，可以用一个字典把F(2)的计算结果存储起来，当再次碰到计算F(2)时就可以直接从字典中取值，改造后的代码如下：package mainimport ( “fmt” “time”)var m = map[int]int{0:0, 1:1}func fib(n int) int { if v, ok :=m[n]; ok { return v } m[n-1],m[n-2] =fib(n-1),fib(n-2) return m[n-1]+m[n-2]}func main() { start := time.Now().UnixNano() fib(45) end := time.Now().UnixNano() fmt.Println(end-start)}经过改造后再计算F(45)不到1秒。一旦某个给定子问题的解已经算出，则将其记忆化存储，以便下次需要同一个子问题解之时直接查表这也是动态规划的重要内容。所以动态规划两个最主要的点是：将一个复杂的问题分解为若干多个子问题。将每个子问题的结果存储起来，使每个子问题只解决一次。House Robber下面是用动态规划的方法来解决 LeetCode 上一道名为 House Robber 的题目：你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。假设现在各个房屋存放的金额分别为2、7、9、3、1，求最大能偷窃到的金额。我们用 P(n) 表示为总共有 n 间房屋时能偷取到的最大金额，用 r(n) 表示为第 n 间房屋中存放的金额。 当 n 为1时 P(1)=r(1)，n 为2时 P(2)=Max(r(1), r(2))。因为题目要求不能打劫相邻两间房，所以当有 n 间房时 P(n)=Max(P(n-2)+r(n), P(n-1))。用方程来表示就是：P(1)=r(1)P(2)=Max(r(1), r(2))P(n)=Max(P(n-2)+r(n), P(n-1))所以这个问题就被分解成了若干个子问题，下面是其代码实现：package mainimport “fmt"var m = map[int]int{}func rob(arr []int) int { l := len(arr) if l <= 0 { return 0 } if v,ok:=m[l-1];ok{ return v } if l == 1 { m[0]=arr[0] return arr[0] } if l == 2 { if arr[0] >= arr[1] { m[1]=arr[0] return arr[0] } else { m[1]=arr[1] return arr[1] } } a, b:= rob(arr[:l-2])+arr[l-1],rob(arr[:l-1]) if a>=b{ m[l-1]=a } else { m[l-1]=b } return m[l-1]}func main() { arr := []int{2,7,9,3,1} m[0]=arr[0] ret :=rob(arr) fmt.Println(ret)}上面的代码就是我们根据方程无脑写出的算法就已经达到了偷窃最大金额的目的，但其实还是有一些优化空间的，我们要计算 P(n) 其实只需要记住之前的 P(n-2) 和 P(n-1)就够了，但我们其实将 P(1)、P(2)、…、P(n-2) 都记住了，带来了一些内存浪费，之所以会有这个问题是因为我们求解 P(n) 时会依次求解 P(n-1)、P(n-2)、…、P(1) 是一种自顶向下的求解方式，如果换成自底向上的求解方式可以写出如下代码：package mainimport “fmt"func rob(arr []int) int { pre1, pre2 := 0, 0 for _,v := range arr { if pre2+v >= pre1 { pre1,pre2 = pre2+v,pre1 } else { pre1,pre2= pre1,pre1 } } return pre1}func main() { arr := []int{2,7,9,3,1} ret :=rob(arr) fmt.Println(ret)}上面的变量 pre1 和 pre2 分别表示 P(n-1) 和 P(n-2)，这样通过自底向上的方式求出了结果，比自顶向下的方式更节省内存。所以动态规划需要记住的几个关键点是将复杂问题拆分成若干个子问题、记住子问题的结果、自顶向下、自底向上。摩尔投票法假如有10个人参与投票，有的人投给A，有的人投给B，有的人投给C，当我们想要找出A、B、C谁得票最多时，我们可以将两个不同的投票作为一对进行删除，直到不能再删时然后再查看结果中还剩下的投票就是得票最多的那个。比如上述10个人的投票情况是[A,B,C,C,B,A,A,A,B,A]，下面是进行删除的过程：[A,B,C,C,B,A,A,A,B,A]==>[C,C,B,A,A,A,B,A] //A,B为不同的投票所以可以 //作为一对进行删除[C,C,B,A,A,A,B,A]==>[C,A,A,A,B,A] //C,C为相同的投票所以不删除，然后 // 再依次向后查找发现C,B不同可以删除 [C,A,A,A,B,A]==>[A,A,B,A][A,A,B,A]==>[A,A] 通过不断的对不同的投票作为一对进行删除，投票结果中最后只剩下了[A,A]，所以A就是得票最多的。摩尔投票法的核心就是将序列中两个不同的元素进行抵消或删除，序列最后剩下一个元素或多个相同的元素，那么这个元素就是出现次数最多的元素。Majority Element求众数就是摩尔投票法的一个典型运用场景，比如有下面这道算法题：给定一个大小为 n 的数组，找到其中的众数。众数是指在数组中出现次数大于 n/2 的元素。给定数组[2,2,1,1,1,2,2,4,5,2,3,2,2] 找出其众数。实现代码如下：package mainimport “fmt"func main() { arr := []int{2,2,1,1,1,2,2,4,5,2,3,2,2} maj, count := arr[0], 1 for i:=1;i<len(arr);i++ { if maj == arr[i] { count++ } else { if count == 0 { maj,count = arr[i],1 continue } count– } } fmt.Println(maj)}代码中先假定数组的第一个元素就是众数，并用一个变量 count 来记录这个众数出现的次数，当被迭代到的数与这个众数相同时 count 就加1，不同时就做抵消操作，即 count 减1，当 count 为0时，就将被迭代到的数设为新的众数并将 count 置1。以上就是摩尔投票法的原理和应用。 ...
该题目有两种解法，都是动态规划中特别经典的解法，一种是最长不下降子序列，一种是最长公共子序列；第一种方法对于该题目其实有点取巧的感觉；首先，注意一点，对于最长不下降子序列来说，其序列的元素一定是非递减的，所以我们的当务之急是如何将值转换为递增序列，从而使得算法能够继续进行；对于这个问题，我们可以使用hashtable进行处理，也就是利用hashtable重新使得值递增；这里需要注意一下，子序列递增研究的是不连续的子序列，连续的子序列其实可以用前面的KMP算法来及进行解决；对于该问题，首当其中的还是状态转移方程。由于该问题还是从0开始研究，所以仍然设置一个一维数组dp来储存中间的状态；大致思路是限定一个子串序列，然后选择一个，从第一个开始进行轮询，这里有点像插入排序的感觉；其状态转移方程为dp[i]=max(1,dp[j]+1);该方程可以理解将第i个元素排在j后面，从而继承j之前的子串序列的长度，1为单个元素的序列长度；代码如下：#include<iostream>#include<stdio.h>#include<stdlib.h>#include<algorithm>using namespace std;const int maxc=210;const int maxn=10010;int Hashtable[maxc];int a[maxn],dp[maxn];int main(){ int n,m,x; scanf("%d%d",&n,&m); memset(Hashtable,-1,sizeof(Hashtable)); for(int i=0;i<m;i++){ scanf("%d",&x); Hashtablet[x]=i; } int L,num=0; scanf("%d",&L); for(int i=0;i<L;i++){ scanf("%d",&x); if(Hashtable[x]>=0){ a[num++]=Hashtable[x]; //进行hashtable的相应转换 } } int ans=-1; for(int i=0;i<num;i++){ dp[i]=1; for(int j=0;j<i;j++){ if(a[j]<=a[i]&&dp[i]<dp[j]+1){ dp[i]=dp[j]+1; } } ans=max(ans,dp[i]); } printf("%d\n",ans); return 0;}第二种不太好理解，所以这里先不再赘述，主要是不能理解为什么公共部分可以重复输出；
这道题也是动态规划的几大问题之一，也就是最大连续序列和问题；对于这个问题，我们需要考虑的首先还是转换方程的问题：我们设置一个dp数组，dp[i]代表的是到当前的最大序列和。所以有转换方程：dp[i]=max(a[i],dp[i-1]+a[i])所以边界就是dp[0]=a[0]，然后从1开始计算；代码如下：#include<iostream>#include<stdlib.h>#include<stdio.h>#include<cstring>#include<string>using namespace std;const int maxn=1010;string data;int matrix[maxn][maxn];int main(){ getline(cin,data); int len=data.size(); for(int i=0;i<len;i++){ matrix[i][i]=1; } int ans=1; for(int i=1;i<len;i++){ if(data[i-1]==data[i]){ matrix[i-1][i]=1; ans=2; } } for(int L=3;L<=len;L++){ for(int i=0;i+L-1<len;i++){ int j=i+L-1; if(data[i]==data[j]&&matrix[i+1][j-1]==1){ matrix[i][j]=1; ans=L; } } } printf("%d\n",ans); system(“pause”); return 0;}
这道题是动态规划几大问题的其中一种，为最长回文子串问题；动态规划个人来说，觉得最重要的就是建立状态转移方程。对于方程变量，我认为最重要的是有几个构成的关键变量；对于这道题，我们着手于i~j个字符，所以关注点在于i和j，所以我们建立一个二维矩阵来保存动态规划途中的计算值。对于dpi，其值为1时，意为i-j的字串是回文子串，为其他值则不是；对于状态转移方程，我们可以这样想：对于一个回文子串，其子串也是回文子串，所以就有方程转移的定律：dpi=dpi+1接下来就是如何遍历；对于遍历，我们一定要保证从边界开始，并且现有计算状态必须建立在已有建立状态之上。由于转换方程的特殊性，i,j两个坐标都像两边扩散，所以我们可以根据L，也就是子串的长度来进行计算；先将单个字符相应的值置为1，然后L=2…..至L=n;在途中记录子串的长度；代码如下所示：#include<iostream>#include<stdlib.h>#include<stdio.h>#include<cstring>#include<string>using namespace std;const int maxn=1010;string data;int matrix[maxn][maxn];int main(){ getline(cin,data); int len=data.size(); for(int i=0;i<len;i++){ matrix[i][i]=1; } int ans=1; for(int i=1;i<len;i++){ if(data[i-1]==data[i]){ matrix[i-1][i]=1; ans=2; } } for(int L=3;L<=len;L++){ for(int i=0;i+L-1<len;i++){ int j=i+L-1; if(data[i]==data[j]&&matrix[i+1][j-1]==1){ matrix[i][j]=1; ans=L; } } } printf("%d\n",ans); system(“pause”); return 0;}
前言最近又看到一篇文章,说到算法对前端的重要性,遂抽出时间(玩的时间),逼着自己看一些相关的知识,当看到动态规划相关文献时,也勾起了很大的兴趣,学习各位大神的博客,有了初步理解,借此记载,可能比较浅显,对于同样初学相关知识的同学,或许会有帮助,如有问题,望大神指出正文学习的最好方法便是带着问题学习,所以首先先采用网上普遍的、对理解动态规划很友好的一个问题作为学习切入点,问题解决后再总结归纳问题:现在有10级台阶,每次只能上1级或2级台阶,问:到达10级台阶的方法有多少?解析:首先按照正常逻辑,看到这个问题或许会懵,因为情况太多无从下手,但是最优解往往需要更改思考方式这里可以从结果考虑,最后我们踩在第10级台阶上,由于每次只能上1 或 2级台阶,所以上一步,我门应该在第9级台阶,或第8级台阶;基于1的结论,从0 到 9 级台阶有多少种方法,对应的从9 到 10级台阶就有多少种方法(这里需要理解下),同理从0 到 8级台阶的方法总数等于从8 到 10级台阶的方法总数,可得从0 到 10级台阶的方法总数(以下简称methods(10))等于 从0 到 9级台阶的方法总数 加 从0 到 8级台阶的方法总数,即methods(10) = methods(9) + methods(8);这里的methods(9) 和 methods(8)就是methods(10)的最优子结构(思维导图有点大,只展示一部分)从第2点我门已经发现了问题的解决逻辑和一点思路,按照第2点的思路,我们将以二叉树的形式将问题分裂成“无数”的子问题,直到分裂成 methods(2) 和 methods(1)时,methods(2)(从0 到 2级台阶的方法数)等于2,而methods(1)等于1,这里的methods(2) 和 methods(1)也就是动态规划里边界由3的结论,我们只需要将所有子问题的解相加便是问题结果,这里将思路转为代码,通过递归实现, methods(n) = methods(n - 1) + methods(n - 2),methods(n - 1) = ……,以此类推 function methods(n) { if (n == 1) return 1 if (n == 2) return 2 console.log(‘计算’) return methods(n - 1) + methods(n - 2) } console.log(methods(10)); // 89问题到这看似已经解决了,但是我想同学在思维导图中应该也发现了,很多子问题是重复的,但是上面代码却做了很多重复工作,很浪费 冗余(如下图),我们希望已经计算过的就不要在重复计算所以优化下, 保存计算过的结果: var resultList = [] // 保存计算过的结果,以计算的台阶数做索引下标 function methods(n) { if (n == 1) return 1 if (n == 2) return 2 if (!resultList[n]) { // 没有就保存 console.log(‘计算’, n) resultList[n] = methods(n - 1) + methods(n - 2) } return resultList[num] }这样看,就节省了很多计算,台阶总数越大,越明显然后咱们再精简下代码:var resultList = [0, 1, 2]; // 对于本题的结果预存了,方便点 function fnSumF(n) { if (!resultList[n]) resultList[n] = fnSumF(n - 1) + fnSumF(n - 2); return resultList[n] }总结动态规划的英文名是Dynamic Programming，是一种分阶段求解决策问题的数学思想;与分治方法类似，都是通过组合子问题的解来来求解原问题的。再来了解一下什么是分治方法，以及这两者之间的差别，分治方法将问题划分为互不相交的子问题，递归的求解子问题，再将它们的解组合起来，求出原问题的解。而动态规划与之相反，动态规划应用与子问题重叠的情况，即不同的子问题具有公共的子子问题（子问题的求解是递归进行的，将其划分为更小的子子问题）。在这种情况下，分治方法会做许多不必要的工作，他会反复求解那些公共子子问题。而动态规划对于每一个子子问题只求解一次，将其解保存在一个表格里面，从而无需每次求解一个子子问题时都重新计算，避免了不必要的计算工作。其实关于和分治的区别,在我们解决问题优化时已经可以看出初学的浅层理解,如有问题希望大家指出,指点,如果问题或者好文章,也希望可以评论推荐学的越多,才发现自己懂得越少 ...
题目Given a string, your task is to count how many palindromic substrings in this string.The substrings with different start indexes or end indexes are counted as different substrings even they consist of same characters.Example 1:Input: “abc"Output: 3Explanation: Three palindromic strings: “a”, “b”, “c”.Example 2:Input: “aaa"Output: 6Explanation: Six palindromic strings: “a”, “a”, “a”, “aa”, “aa”, “aaa”.Note:The input string length won’t exceed 1000.题目地址讲解题目的意思是：找出字符串中所有回文串，不同位置的回文串不算同一个。这道题我只能想到从左到右按照从1到s.length的长度依次扫N遍。而且这还不包括判断是否是回文串这一步所用的时间。而判断回文串显然是可以有重复计算的子问题的，所以要用到动态规划。依旧是用规模从大到小的备忘录递归解法。这道题做下来还是挺轻松的，我发现我越来越喜欢用递归了，对递归的掌控力也变强了。java代码class Solution { private boolean[][] dp; public int countSubstrings(String s) { int result=0; dp = new boolean[s.length()][s.length()]; for(int i=0;i<s.length();i++){ for(int j=0;j+i<s.length();j++){ dynamicProgramming(s, j, j+i); } } for(int i=0;i<dp.length;i++){ for(int j=0;j<dp[i].length;j++){ // System.out.println(i+”,"+j+"="+dp[i][j]); if(dp[i][j]){ result++; } } } return result; } private boolean dynamicProgramming(String s, int left, int right){ if(left==right){ dp[left][right] = true; return dp[left][right]; } if(dp[left][right]){ return dp[left][right]; } if(s.charAt(left)!=s.charAt(right)){ dp[left][right] = false; return dp[left][right]; }else{ if(right-left>1){ dp[left][right] = dynamicProgramming(s, left+1, right-1); return dp[left][right]; }else{ dp[left][right] = true; return dp[left][right]; } } }} ...
题目Alex and Lee play a game with piles of stones. There are an even number of piles arranged in a row, and each pile has a positive integer number of stones piles[i].The objective of the game is to end with the most stones. The total number of stones is odd, so there are no ties.Alex and Lee take turns, with Alex starting first. Each turn, a player takes the entire pile of stones from either the beginning or the end of the row. This continues until there are no more piles left, at which point the person with the most stones wins.Assuming Alex and Lee play optimally, return True if and only if Alex wins the game.Example 1:Input: [5,3,4,5]Output: trueExplanation: Alex starts first, and can only take the first 5 or the last 5.Say he takes the first 5, so that the row becomes [3, 4, 5].If Lee takes 3, then the board is [4, 5], and Alex takes 5 to win with 10 points.If Lee takes the last 5, then the board is [3, 4], and Alex takes 4 to win with 9 points.This demonstrated that taking the first 5 was a winning move for Alex, so we return true.Note:2 <= piles.length <= 500piles.length is even.1 <= piles[i] <= 500sum(piles) is odd.题目地址讲解动态规划，好久没做动态规划了。三要素：最优子结构、无后效性、子问题重叠。核心思想是记录子问题的解（空间换时间）。具体做法有 自底向上（迭代，规模由小到大），自顶向下（递归，规模由大到小）。Java代码自顶向下：递归的比较好理解一点，状态转移方程：f(n) = {拿左边+f(n-1)左， 拿右边+f(n-1)右}class Solution { int beginIndex; int endIndex; int[][] dp; public boolean stoneGame(int[] piles) { beginIndex = 0; endIndex = piles.length-1; dp = new int[piles.length][piles.length]; for(int i=0;i<dp.length;i++){ for(int j=0;j<dp[i].length;j++){ dp[i][j]=-1; } } int sum=0; for(int x:piles){ sum += x; } return Math.max(piles[beginIndex]+stoneGame(piles, beginIndex+1, endIndex), piles[endIndex]+stoneGame(piles, beginIndex, endIndex-1))>sum/2?true:false; } private int stoneGame(int[] piles, int begin, int end){ if(begin>=end){ return 0; } if(dp[begin][end]!=-1){ return dp[begin][end]; }else{ dp[begin][end] = Math.max(piles[begin]+stoneGame(piles, begin+1, end), piles[end]+stoneGame(piles, begin, end-1)); return dp[begin][end]; } }}自底向上：把另一个人拿的数当做减。求piles[i]到piles[j]的最优解，并存起来。class Solution { public boolean stoneGame(int[] piles) { int[][] dp = new int[piles.length][piles.length]; for(int i=0;i<piles.length;i++){ for(int j=i+1;j<piles.length;j++){ int parity= (j-i)%2; if(parity==1){ dp[i][j] = Math.max(piles[i]+dp[i+1][j], piles[j]+dp[i][j-1]); }else{ dp[i][j] = Math.max(-piles[i]+dp[i+1][j], -piles[j]+dp[i][j-1]); } } } return dp[0][piles.length-1]>0; }} ...