Dynamic-Programming

源代码下载： dynamic-programming-cn.html.markdown 动静布局简介动静布局是一种实用的技巧，它能够用来解决一系列特定问题。它的思路很简略，如果你对某个给定的输出解决了一个问题，那么你能够保留已有信息，以防止反复计算，节约计算工夫。 记住，如果遗记历史，就要被迫做更多的苦力。斐波那契数列就是一个显然的例子。 解决问题的形式自顶向下 : 利用分支策略合成问题。如果你曾经解决过以后子问题了，那么就返回已有信息。如果以后子问题没有计算过，那么就对它进行计算。这样的办法很易于思考、很直观。这被称作“记忆化”。自底向上 : 首先剖析问题，将问题合成为不同规模的问题，并决定它们的程序，按程序计算，直到解决给定规模的问题。这样的流程能够保障在解决较大的问题之前解决（它所依赖的）较小的问题。这种流程被称作“动静布局”。动静布局的例子最长回升子序列问题。给定S= {a[1] , a[2] , a[3], a[4], ............., a[n-1], a[n] }，求出一个子序列，使得对于所有在这个子序列中所有满足j<i的j与i，满足aj<ai。首先咱们要探讨以原序列的第i个元素结尾的最长回升子序列dp[i]。那么答案是整个dp序列的最大值。思考dp[i]，它的最初一个元素为a[i]。枚举它的倒数第二个元素a[j]，则a[j]<a[i]成立。则dp[i]就是所有这样的dp[j]的最大值加上1(最初一个元素)。这个算法具备O(n^2)的工夫复杂度。 此算法的伪代码： for i=0 to n-1 dp[i]=0 for j=0 to i-1 if (a[i] > a[j] and dp[i]<dp[j]) LS[i] = LS[j] dp[i]=dp[i]+1for i=0 to n-1 if (largest < dp[i]) largest = dp[i]这个算法的复杂度能够通过将数组换为其余数据结构来优化，来取得O(n * log n)的工夫复杂度。 同样的思路能够求出有向无环图上的最大门路。 一些驰名的动静布局问题及其实现Floyd Warshall 算法 - 教程与C实现源码整数背包问题 - 教程与C实现源码最长公共子序列问题 - 教程与C实现源码 在线资源codechef洛谷有倡议？或者发现什么谬误？在Github上开一个issue，或者发动pull request！ 原文由Akashdeep Goel编写，并由0个好心人批改。Translated by: EtaoinWu© 2022 Akashdeep Goel本作品采纳 CC BY-SA 3.0 协定进行许可。

题目要求A sequence of numbers is called arithmetic if it consists of at least three elements and if the difference between any two consecutive elements is the same.For example, these are arithmetic sequences:1, 3, 5, 7, 97, 7, 7, 73, -1, -5, -9The following sequence is not arithmetic.1, 1, 2, 5, 7 A zero-indexed array A consisting of N numbers is given. A subsequence slice of that array is any sequence of integers (P0, P1, ..., Pk) such that 0 ≤ P0 < P1 < ... < Pk < N.A subsequence slice (P0, P1, ..., Pk) of array A is called arithmetic if the sequence A[P0], A[P1], ..., A[Pk-1], A[Pk] is arithmetic. In particular, this means that k ≥ 2.The function should return the number of arithmetic subsequence slices in the array A.The input contains N integers. Every integer is in the range of -231 and 231-1 and 0 ≤ N ≤ 1000. The output is guaranteed to be less than 231-1. Example:Input: [2, 4, 6, 8, 10]Output: 7Explanation:All arithmetic subsequence slices are:[2,4,6][4,6,8][6,8,10][2,4,6,8][4,6,8,10][2,4,6,8,10][2,6,10]从一个无序的整数数组中，找到所有等差子数列的数量。这里需要注意，等差子数列要求从原数组中找出Pk个下标的元素，其中P0 < P1 < P2... < Pk，且满足A[P1]-A[P0] = A[P2] - A[P1] ... = A[Pk]-A[Pk-1]。 ...

题目要求Consider the string s to be the infinite wraparound string of "abcdefghijklmnopqrstuvwxyz", so s will look like this: "...zabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcd....".Now we have another string p. Your job is to find out how many unique non-empty substrings of p are present in s. In particular, your input is the string p and you need to output the number of different non-empty substrings of p in the string s.Note: p consists of only lowercase English letters and the size of p might be over 10000.Example 1:Input: "a"Output: 1Explanation: Only the substring "a" of string "a" is in the string s.Example 2:Input: "cac"Output: 2Explanation: There are two substrings "a", "c" of string "cac" in the string s.Example 3:Input: "zab"Output: 6Explanation: There are six substrings "z", "a", "b", "za", "ab", "zab" of string "zab" in the string s.假设存在一个从a-z26个字母无限循环的字符串s，现在输入一个字符串p，问该字符串有多少个子字符串在s中循环出现？ ...

题目要求In the computer world, use restricted resource you have to generate maximum benefit is what we always want to pursue.For now, suppose you are a dominator of m 0s and n 1s respectively. On the other hand, there is an array with strings consisting of only 0s and 1s.Now your task is to find the maximum number of strings that you can form with given m 0s and n 1s. Each 0 and 1 can be used at most once.Note:The given numbers of 0s and 1s will both not exceed 100The size of given string array won't exceed 600. Example 1:Input: Array = {"10", "0001", "111001", "1", "0"}, m = 5, n = 3Output: 4Explanation: This are totally 4 strings can be formed by the using of 5 0s and 3 1s, which are “10,”0001”,”1”,”0” Example 2:Input: Array = {"10", "0", "1"}, m = 1, n = 1Output: 2Explanation: You could form "10", but then you'd have nothing left. Better form "0" and "1".已知有m个0和n个1，问最多能构成数组中多少个数字。已知每个0和1只能使用一次。 ...

原作者：金子冴校阅：内野良一翻译：叶子原文链接目录什么是动态规划(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)之外的所有计算都不止一次。 ...

题目要求Given an array which consists of non-negative integers and an integer m, you can split the array into m non-empty continuous subarrays. Write an algorithm to minimize the largest sum among these m subarrays.Note:If n is the length of array, assume the following constraints are satisfied:1 ≤ n ≤ 10001 ≤ m ≤ min(50, n)Examples:Input:nums = [7,2,5,10,8]m = 2Output:18Explanation:There are four ways to split nums into two subarrays.The best way is to split it into [7,2,5] and [10,8],where the largest sum among the two subarrays is only 18.将一个长度为n的正整数数组分割为m个非空的连续子数组，并分别计算每个子数组中所有元素的和。求一种分割方式，使得该分割方式生成的最大子数组和为所有分割方式中最小的。 ...

题目要求A sequence of numbers is called a wiggle sequence if the differences between successive numbers strictly alternate between positive and negative. The first difference (if one exists) may be either positive or negative. A sequence with fewer than two elements is trivially a wiggle sequence.For example, [1,7,4,9,2,5] is a wiggle sequence because the differences (6,-3,5,-7,3) are alternately positive and negative. In contrast, [1,4,7,2,5] and [1,7,4,5,5] are not wiggle sequences, the first because its first two differences are positive and the second because its last difference is zero.Given a sequence of integers, return the length of the longest subsequence that is a wiggle sequence. A subsequence is obtained by deleting some number of elements (eventually, also zero) from the original sequence, leaving the remaining elements in their original order.Example 1:Input: [1,7,4,9,2,5]Output: 6Explanation: The entire sequence is a wiggle sequence.Example 2:Input: [1,17,5,10,13,15,10,5,16,8]Output: 7Explanation: There are several subsequences that achieve this length. One is [1,17,10,13,10,16,8].Example 3:Input: [1,2,3,4,5,6,7,8,9]Output: 2Follow up:Can you do it in O(n) time?扭动序列是指数组中的相邻两个元素的差保证严格的正负交替，如[1,7,4,9,2,5]数组中相邻两个元素的差为6,-3,5,-7,3，满足扭动序列的要求。现在要求从一个数组中，找到长度最长的扭动子序列，并返回其长度。 ...

题目要求A frog is crossing a river. The river is divided into x units and at each unit there may or may not exist a stone. The frog can jump on a stone, but it must not jump into the water.Given a list of stones’ positions (in units) in sorted ascending order, determine if the frog is able to cross the river by landing on the last stone. Initially, the frog is on the first stone and assume the first jump must be 1 unit.If the frog’s last jump was k units, then its next jump must be either k - 1, k, or k + 1 units. Note that the frog can only jump in the forward direction.Note:The number of stones is ≥ 2 and is < 1,100.Each stone’s position will be a non-negative integer < 231.The first stone’s position is always 0.Example 1:[0,1,3,5,6,8,12,17]There are a total of 8 stones.The first stone at the 0th unit, second stone at the 1st unit,third stone at the 3rd unit, and so on…The last stone at the 17th unit.Return true. The frog can jump to the last stone by jumping 1 unit to the 2nd stone, then 2 units to the 3rd stone, then 2 units to the 4th stone, then 3 units to the 6th stone, 4 units to the 7th stone, and 5 units to the 8th stone.Example 2:[0,1,2,3,4,8,9,11]Return false. There is no way to jump to the last stone as the gap between the 5th and 6th stone is too large.假设有一只青蛙需要过河，河中会有一些石子，青蛙必须踩在石头上才算成功。石头的位置用整数数组来表示。青蛙的行走规则为：假设上一次青蛙跳了k格，则当前青蛙只能跳k-1或k或k+1格，且青蛙只能向前跳，不能向后跳。广度优先遍历可以从起点开始，对从该点出发的所有可能步数进行遍历，并更新从该点可达的点的所有的可行步数。利用Map<Integer, Set<Integer>>数据结构来记录该结果，其中map的key为stone的unit数，它的value对应的是从该key出发的所有的上一步的步长。该遍历思路类似于广度优先遍历，即将该点出发遍历所有的可达点。代码如下： public boolean canCross(int[] stones) { if(stones.length < 2) return true; if(stones.length == 2 && stones[1] == 1) return true; if(stones.length >= 2 && stones[1] != 1) return false; Map<Integer, Set<Integer>> stoneJump = new HashMap<>(); for(int i = 1 ; i<stones.length ; i++) { stoneJump.put(stones[i], new HashSet<>()); } stoneJump.get(1).add(1); int finalStone = stones[stones.length-1]; boolean hasNext = false; for(int i = 1 ; i<stones.length; i++) { for(int step : stoneJump.get(stones[i])) { int next = stones[i] + step - 1; for(int addOn = -1 ; addOn <= 1 ; addOn++) { if(step + addOn != 0) { if(next == finalStone) { return true; } if(stoneJump.containsKey(next)) { stoneJump.get(next).add(step + addOn); hasNext = true; } } next++; } } if(!hasNext) break; hasNext = false; } return false; }深度优先遍历和上一种思路的区别在于，这种方法会尽可能往远处遍历。即只要该点可以到达下一点，则会立刻尝试从一点到达终点。代码如下： public boolean canCross(int[] stones) { for(int i = 1 ; i<stones.length ; i++) { if(stones[i] - stones[i-1] > i) return false; } return canCross2(stones, 1, 1); } public boolean canCross2(int[] stones, int idx, int lastStep) { if(idx == stones.length-1) return true; if(idx < 0 || lastStep <= 0) return false; for(int jump = lastStep + 1 ; jump >= lastStep -1 ; jump–) { if(canCross2(stones, Arrays.binarySearch(stones, stones[idx] + jump), jump)){ return true; } } return false; } ...

题目要求Given a non-empty array containing only positive integers, find if the array can be partitioned into two subsets such that the sum of elements in both subsets is equal.Note:1.Each of the array element will not exceed 100.2.The array size will not exceed 200.Example 1:Input: [1, 5, 11, 5]Output: trueExplanation: The array can be partitioned as [1, 5, 5] and [11].Example 2:Input: [1, 2, 3, 5]Output: falseExplanation: The array cannot be partitioned into equal sum subsets.假设有一个全为正整数的非空数组，将其中的数字分为两部分，确保两部分数字的和相等。思路和代码这和0-1背包问题是完全一样的，01背包问题是指假设有n个物品，每个物品中为weight[i]，假设背包的承重为k，问如何选择物品使得背包中的承重最大。而这里的问题等价于，有n个物品，每个物品承重为input[i]，问如何挑选物品，使得背包的承重搞好为所有物品重量和的一般。假设我们已经知道前i个物品是否能够构成重量k，我们令该值为dpi，那么第i+1个物品是否能够构成重量取决于dpi和dpi], 即i+1个物品能够构成重量k有两种情况，第一种选择了i+1个物品，则要寻找前i个物品是否构成k-input[i+1]的重量，第二种就是没有选择第i+1个物品，则直接判断前i个物品是否已经构成了k的重量。代码如下： public boolean canParition(int[] nums) { int sum = 0; for(int n : nums) { sum += n; } if(sum % 2 != 0) return false; int half = sum / 2; boolean[][] sums = new boolean[nums.length+1][half+1]; for(int i = 0 ; i<=nums.length ; i++) { for(int j = 0 ; j<=half ; j++) { if(i==0 && j==0){ sums[i][j] = true; }else if(i==0) { sums[i][j] = false; }else if(j==0){ sums[i][j] = true; }else { sums[i][j] = sums[i-1][j] || (nums[i-1] <= j ? sums[i-1][j-nums[i-1]] : false); } } } return sums[nums.length][half]; } ...

题目要求We are playing the Guess Game. The game is as follows:I pick a number from 1 to n. You have to guess which number I picked.Every time you guess wrong, I’ll tell you whether the number I picked is higher or lower.However, when you guess a particular number x, and you guess wrong, you pay $x. You win the game when you guess the number I picked.Example:n = 10, I pick 8.First round: You guess 5, I tell you that it’s higher. You pay $5.Second round: You guess 7, I tell you that it’s higher. You pay $7.Third round: You guess 9, I tell you that it’s lower. You pay $9.Game over. 8 is the number I picked.You end up paying $5 + $7 + $9 = $21.Given a particular n ≥ 1, find out how much money you need to have to guarantee a win.一个猜数字游戏，数字区间为1~n，每猜一次，会有人告诉你猜中了或者当前的数字是大于结果值还是小于结果值。猜对则本次猜测免费，猜错则本次猜测需要花费和数字等额的金钱。问如果要确保能够猜中数字，最少要花费多少钱。其实这题的英文表述有些问题，确切来说，在所有能够确保找到目标值的方法中，找到花费金钱最少的哪种。思路我们先用一个比较简单的数字来找规律。当n等于3时，即从1,2,3中找到目标数字，确保找到一个数字至少需要多少钱。查询序列如下：目标值3：1,2 2目标值2：1,3目标值1：3,2,2可见如果要找到1，2，3中任意一个数字，最少要花费2元钱，即从2开始查询，如果命中，则花费0元，如果没有命中也知道目标值比2小还是比2大，下次猜测一定命中，因此该序列中找到任何一个数字最多花费2元钱。如此可见，假如要知道min(1,n)的值，只要找到花费最小的中间点k，即递归的公式相当于min(1,n) = k + Math.max(min(1, k-1), min(k+1,n)) 1<=k<=n找到最小的min即可。思路一：自顶向下的动态规划 public int getMoneyAmount(int n) { int[][] tmp = new int[n+1][n+1]; for(int[] row: tmp){ Arrays.fill(row, Integer.MAX_VALUE); } return getMoneyAmount(n, 1, n, tmp); } public int getMoneyAmount(int n, int lft, int rgt, int[][] tmp) { if(lft>=rgt) return 0; if(tmp[lft][rgt] != Integer.MAX_VALUE) return tmp[lft][rgt]; for(int i = lft ; i<=rgt ; i++) { tmp[lft][rgt] = Math.min(tmp[lft][rgt], Math.max(i + getMoneyAmount(n, lft, i-1, tmp), i + getMoneyAmount(n, i+1, rgt, tmp))); } return tmp[lft][rgt]; }思路二：自底向上的动态规划 public int getMoneyAmount(int n) { int[][] dp = new int[n+1][n+1]; for(int i = 2 ; i<=n ; i++) { for(int j = i-1 ; j>0 ; j–) { int min = Integer.MAX_VALUE; for(int k = j+1 ; k<i ; k++) { min = Math.min(min, k + Math.max(dp[j][k-1], dp[k+1][i])); } dp[j][i] = j + 1 == i ? j : min; } } return dp[1][n]; } ...

题目要求Given an integer array with all positive numbers and no duplicates, find the number of possible combinations that add up to a positive integer target.Example:nums = [1, 2, 3]target = 4The possible combination ways are:(1, 1, 1, 1)(1, 1, 2)(1, 2, 1)(1, 3)(2, 1, 1)(2, 2)(3, 1)Note that different sequences are counted as different combinations.Therefore the output is 7.Follow up:What if negative numbers are allowed in the given array?How does it change the problem?What limitation we need to add to the question to allow negative numbers?有一个不包含重复值的正整数数组nums，问从数组中选择几个数，其和为target，这样的数的组合有几种？思路一：自顶向下的dp这题本质上需要注意一点，就是我如果需要组成target，那么一定是由nums中的一个值和另一个值的排列组合结果构成的。比如com[4] = com[4-1] + com[4-2] + com[4-1]。通过这一点，我们构成一个递归表达式，但是因为单纯的递归表达式没有计算中间结果，所以会造成大量重复的计算影响效率，所以这里采用dp的思路额外的用数组来记录已经计算过的com结果。比如com[3] = com[2] + com[1], com[2] = com[1]，如果没有dp，则需要重复计算com[1]的结果。 public int combinationSum4(int[] nums, int target) { if (nums == null || nums.length < 1) { return 0; } int[] dp = new int[target + 1]; Arrays.fill(dp, -1); dp[0] = 1; return helper(nums, target, dp); } private int helper(int[] nums, int target, int[] dp) { if (dp[target] != -1) { return dp[target]; } int res = 0; for (int i = 0; i < nums.length; i++) { if (target >= nums[i]) { res += helper(nums, target - nums[i], dp); } } dp[target] = res; return res; }思路二：自底向上dp public int combinationSum4(int[] nums, int target) { Arrays.sort(nums); int[] combinationCount = new int[target+1]; combinationCount[0] = 1; for(int i = 1 ; i<=target ; i++) { for(int j = 0 ; j<nums.length && nums[j] <= i ; j++) { combinationCount[i] += combinationCount[i - nums[j]]; } } return combinationCount[target]; } ...

题目要求Given a set of distinct positive integers, find the largest subset such that every pair (Si, Sj) of elements in this subset satisfies:Si % Sj = 0 or Sj % Si = 0.If there are multiple solutions, return any subset is fine.Example 1:Input: [1,2,3]Output: [1,2] (of course, [1,3] will also be ok)Example 2:Input: [1,2,4,8]Output: [1,2,4,8]假设有一组值唯一的正整数数组，找到元素最多的一个子数组，这个子数组中的任选两个元素都可以构成Si % Sj = 0 或 Sj % Si = 0。思路和代码这题最核心的思路在于，假如知道前面k个数字所能够组成的满足题意的最长子数组，我们就可以知道第k+1个数字所能构成的最长子数组。只要这个数字是前面数字的倍数，则构成的数组的长度则是之前数字构成最长子数组加一。这里我们使用了两个临时数组count和pre，分别用来记录到第k个位置上的数字为止能够构成的最长子数组，以及该子数组的前一个可以被整除的值下标为多少。 public List<Integer> largestDivisibleSubset(int[] nums) { int[] count = new int[nums.length]; int[] pre = new int[nums.length]; Arrays.sort(nums); int maxIndex = -1; int max = 0; for(int i = 0 ; i<nums.length ; i++) { count[i] = 1; pre[i] = -1; for(int j = i-1 ; j>=0 ; j–) { if(nums[i] % nums[j] == 0 && count[j] >= count[i]){ count[i] = count[j] + 1; pre[i] = j; } } if(count[i] > max) { max = count[i]; maxIndex = i; } } List<Integer> result = new ArrayList<Integer>(); while(maxIndex != -1){ result.add(nums[maxIndex]); maxIndex = pre[maxIndex]; } return result; } ...