动态规划初探及什么是⽆后效性？（转）对于动态规划，我是这样理解的：把待解决的问题分为⼀个规模较原问题⼩的⼦问题、然后要考虑的就是如何更具这个⼦问题如何得到原问题的解以及如何解决这个⼦问题当然、原问题和⼦问题需要有相同的解决⽅式、它们只有问题规模的区别。
这样讲有点抽象、⽤⼀个简单的图来说明下：可以简单的这样理解、把原问题划分为⼩的问题（能组合成原问题的，⼩的问题再划分、持续下去，找到简单解反⽅向计算回来（记下每⼀步结果）最后就能得到解。
听起来似乎不难，但是要作⽐较深⼊的理解还是得通过实例说话有向⽆环图的最长简单路径：对于⼀般的图，求最长路径并不向最短路径那样容易，因为最长路径并没有最优⼦结构的属性。
但DGA例外问题描述：给⼀个带权有向⽆环图G=（V，E），找出这个图⾥的最长路径。
说实话初学者直接给出这个图会看蒙的、再看看问题，不知道从何下⼿。
好了，对上图做个简单的处理：现在看起来是不是清晰多了呢⽤dilg(v)表⽰以点结尾的最长路径，现在考虑dilg(D), dilg(B), dilg(C)dilg(D)=max{dilg(B)+1, dilg(C)+3}来解释⼀下：点D的⼊度边有CD、BD。
以D结尾的最短路径必定经过C、B中的⼀点；如果是C点，则以dilg(C)+3(权值)定会⼤于等于dilg(B)+1(权值)如果没能看懂，请注意dilg(V)的定义对于任意的点V可以有如下表达式：dilg(v)=max{dilg(u)+w(u, v)，(u,v)∈E}这样、问题dilg(V)就会被转化为较⼩的⼦问题dilg(U)（当然，U是连⼊V的点）任何⼀个问题都可以⽤这样的⽅式转化、变⼩。
但总不能⽆限变⼩啊，最后回成为最简单的问题。
当有两个点，且其中的⼀个点⼊度为0的时候如图中的S-->C他们的最长距离就是权值2。
⼊门篇中说过，思考⽅向是从复杂到简单，⽽计算⽅向是从简单到复杂。
算法如下Initialize all dilg(.) values to ∞;1.Let S be the set of vertices with indegree=0; ////设集合S，⾥⾯的是⼊度为0的点2.For each vertex v in S do dilg(v)=0;3. For each v∈V\S in Topological Sorting order do //对于V中除S外的点、按照拓扑排序的顺序，依次求出最长路径并保存好 dilg(v)=max{dilg(u)+w(u, v)，(u,v)∈E} //拓扑排序可以简单的理解为从起点到终点的最短路径4. Return the dilg(v) with maximum value.现在是找到最长路径的⼤⼩了、但是如何得到最长路径呢？只需做点⼩⼩的改动：Let S be the set of vertices with indegree=0;for each vertex v in S dodist(v)=0;4. For each v∈V\S in Topological Sorting order dodilg(v)=max(u,v)∈E{dilg(u)+w(u, v)}let (u,v) be the edge to get the maximumvalue;dad(v)=u;5. Return the dilg(.) with maximum value.每⼀步都记下V的⽗节点、最后根据dad()数组即可得到路径。
Dynamic Programming方法概述在Divide and Conquer的時候，如果一次會分成數個子問題，很容易就會要重複計算一些子問題，這樣非常浪費時間。
所以我們建一張表，把所有子問題的答案存下來，下次再碰到時，就可以直接用。
這是由上而下的做法。
我們也可以倒過來，由下往上做，就是先把可能遇到的子問題都處理好，再一步一步推回原本的問題。
用Dynamic Programming，最重要的是「DP元素」和「遞迴式」。
「DP元素」就是表格上每一格存的東西所代表的意義；「遞迴式」就是用子問題答案建構出原問題答案的方法。
通常決定了這兩樣東西，就可以很容易的寫出程式。
而這兩樣東西的好壞，會決定這個演算法的好壞。
如果題目不只求最佳解的值是多少，還要問「如何解」，那多半需要把DP 過程中所做的選擇記錄下來，然後從最後面trace-back回去。
題1 生產線現在有兩條生產線，每條線有n個工作站，第a條線上的第b個站需要A a,b 的時間。
每一個貨物都要依序經過n個工作站（無論在哪條線上），才能出廠。
從工作站W1,x到W1,x+1不需要花時間，但是從W1,x到W2,x+1需要T1,x的時間；同樣的，從W2,x到W1,x+1需要T2,x的時間。
進入生產線和從生產線送出分別需要E1、E2、X1、X2的時間。
給定這些時間，若想以最快的方式生產一件產品，要經過哪些工作站？DP元素：Time[a, b] 表示第a條生產線第b個站到出口所需的最短時間遞迴式：Time[a, b] = min{ Time[a, b+1], Time[3-a, b+1] + T a,b }題2 Longest Common Subsequence（最長共同子序列）定義：字串p為字串s的subsequence 若且唯若p的每個字元都按照順序出現在s中。
（不一定要連續，連續的又稱為substring）例如字串”abc”的subsequence有“”、“a”、“b”、“c”、“ab”、“bc”、“ac”、“abc”。
〔有翻译〕1.The O-notation provides an asymptotic upper bound. The -notationprovides an asymptotic lower bound. The Θ-notation asymptoticallya function form above and below.2.To represent a heap as an array，the root of tree is A[1], and giventhe index i of a node, the indices of its parent Parent(i) { return ëi/2û; }，left child,Left(i) { return 2*i; }，right child, right(i) { return 2*i + 1; }.代表一个堆中的一个数组，树的根节点是A[1]，并且给出一个节点i，那么该节点的父节点是左孩子右孩子3.Because the heap of n elements is a binary tree, the height of anynode is at most Q(lg n).因为n个元素的堆是一个二叉树，任意节点的树高最多是4.In optimization problems, there can be many possible solutions. Eachsolution has a value, and we wish to find a solution with the optimal (minimum or maximum) value. We call such a solution an optimal solution to the problem.在最优化问题中，有很多可能的解，每个解都有一个值，我们希望找到一个最优解〔最大或最小〕，我们称这个解为最优解问题。
ccf序列查询新解英文回答：CCF sequence is a series of numbers that follows a specific pattern. It is a well-known sequence in mathematics and has been studied extensively. As for the new solution to query CCF sequence, there are a few approaches that can be taken.One possible solution is to use dynamic programming. We can pre-calculate the CCF sequence up to a certain number and store it in an array. Then, when a query is made, we can simply look up the corresponding value in the array. This approach has a time complexity of O(1) for each query, as the value is already pre-calculated.Another solution is to use a recursive function. We can define a function that takes an input number and returns the corresponding value in the CCF sequence. This function can then be called whenever a query is made. However, thisapproach may have a higher time complexity, depending onthe implementation.For example, let's say we have a CCF sequence definedas follows:CCF(n) = CCF(n-1) + CCF(n-2) + CCF(n-3)。
