c語言dp演算法思想

㈠ 想知道dp演算法是什麼呢

DP演算法是用於求解具有某種最優性質的問題的一種常用方法。

動態規劃與其它演算法相比，大大減少了計算量，豐富了計算結果，不僅求出了當前狀態到目標狀態的最優值，而且同時求出了到中間狀態的最優值，這對於很多實際問題來說是很有用的。

動態規劃相比一般演算法也存在一定缺點：空間占據過多，但對於空間需求量不大的題目來說，動態規劃無疑是最佳方法，動態規劃演算法和貪婪演算法都是構造最優解的常用方法。動態規劃演算法沒有一個固定的解題模式，技巧性很強。

動態規劃基本思想：一般來說，只要問題可以劃分成規模更小的子問題，並且原問題的最優解中包含了子問題的最優解，則可以考慮用動態規劃解決。

動態規劃的實質是分治思想和解決冗餘，因此，動態規劃是一種將問題實例分解為更小的、相似的子問題，並存儲子問題的解而避免計算重復的子問題，以解決最優化問題的演算法策略。

㈡ dp演算法是什麼

動態規劃演算法（Dynamic Programming），是將復雜問題拆分成子問題，並在子問題的基礎上，求解復雜問題，子問題之間不是獨立的，而是相互依存的。

動態規劃過程是：每次決策依賴於當前狀態，又隨即引起狀態的轉移。一個決策序列就是在變化的狀態中產生出來的，所以，這種多階段最優化決策解決問題的過程就稱為動態規劃（DP）。

動態規劃演算法有兩種實現形式：遞歸，非遞歸。

動態規劃的演算法設計

1、找出最優解的性質，並描述其結構特徵。

2、遞歸定義最優值。

3、以自底向上的方式計算最優值。

4、根據計算最優值時得到的信息構造出最優解。

㈢ dp的演算法是什麼

DP演算法是解決多階段決策過程最優化問題的一種常用方法。

多階段決策過程是指這樣一類特殊的活動過程，過程可以按時間順序分解成若干個相互聯系的階段，在每一個階段都需要做出決策，全部過程的決策是一個決策序列。

動態規劃演算法是解決多階段決策過程最優化問題的一種常用方法，難度比較大，技巧性也很強。利用動態規劃演算法，可以優雅而高效地解決很多貪婪演算法或分治演算法不能解決的問題。

原理

動態規劃問世以來，在經濟管理、生產調度、工程技術和最優控制等方面得到了廣泛的應用。例如最短路線、庫存管理、資源分配、設備更新、排序、裝載等問題，用動態規劃方法比用其它方法求解更為方便。

雖然動態規劃主要用於求解以時間劃分階段的動態過程的優化問題，但是一些與時間無關的靜態規劃(如線性規劃、非線性規劃)，只要人為地引進時間因素，把它視為多階段決策過程，也可以用動態規劃方法方便地求解。

㈣ C語言*fp = *dp如何理解

fp地址的間接訪問到的空間被賦予dp地址下所存儲的值，這么說可能有點繞口吧。。。就是說dp和fp都是指針地址，把fp地址下的空間賦值為dp的地址空間下所存儲的值

㈤ dp演算法是什麼呢

dp演算法就是動態規劃，是運籌學的一個分支，是求解決策過程最優化的過程。

動態規劃方法一般用來求解最優化問題。這類問題可以有很多可行解，每個解都有一個值，我們希望找到具有最優值的解，我們稱這樣的解為問題的一個最優解，而不是最優解，因為可能有多個解都達到最優值。

動態規劃過程介紹：

確定動態規劃三要素，整個求解過程就可以用一個最優決策表來描述，最優決策表是一個二維表，其中行表示決策的階段，列表示問題狀態。

表格需要填寫的數據一般對應此問題的在某個階段某個狀態下的最優值（如最短路徑，最長公共子序列，最大價值等），填表的過程就是根據遞推關系，從1行1列開始，以行或者列優先的順序，依次填寫表格，最後根據整個表格的數據通過簡單的取捨或者運算求得問題的最優解。

㈥ C語言，最長上升子序列數,,

最長上升子序列（LIS）
問題描述：設現在有一串序列，要求找出它的一串子序列，這串子序列可以不連續，但必須滿足它是嚴格的單調遞増的且為最長的。把這個長度輸出。
示例：1 7 3 5 9 4 8 結果為4
題例：參看POJ 2533
解法：
1. DP之O(n2)演算法：先按DP的思想來分析一下，要想求n個數的最長上升子序列，設有數據數組data[n]和狀態數組dp[n]，則對其尾元素data[n]來說，它的最長上升子序列就是它自己，即dp[n]=1，而當把它的前一個元素data[n-1]考慮進來時，如果data[n-1]<data[n]則會存在一個長度為2的上升子序列，如果data[n-1]>data[n]那麼這個長度仍會是1。當把這個思想一般化的時候，對於任意一個元素data[k]來說，我們需要找出在data[k]以後的元素中比data[k]大，並且最長的一個序列做為它的後繼。這樣dp[k]就可以寫成dp[k+1]+1。現在我們定義一個量dp[k]=m，它代表著到第k個元素為止（可以包含k也可以不包含k），它的最長上升序列的長度為m。仔細體會dp[k]=m的意義，這裡面的k是可包括在內，也可以不包括在內的（與之前的最大子序列和不同）。要想確定這個m的值，就必須找到一個在第k個元素之前的一個元素的值小於data[k]的值，並且那個元素所對應的dp值是找到的滿足第一個條件前提下dp值最大的一個。這就意味著我們需要內層遍歷之前算出來的dp值，所以需要兩層循環來實現這個演算法。這樣我們就可以總結出狀態轉移方程為dp[k]=max(dp[i](1<=i<=k&&a[i]<a[k])+1。其中找dp[i]的過程我們需要用一層循環來實現，而找dp[k]的過程也要一層循環，所以我們得到了O(n2)的演算法。
dp[k]=max(dp[i])+1 其中i滿足(1<=i<=k&&a[i]<a[k])
常式：
#include <stdio.h>
const int inf = -0x3fffffff;
int main(void)
{
int i,j,len,max,res,data[] = {1,7,3,5,9,4,8},dp[20]={1};
len = sizeof(data)/sizeof(int);
res = max = inf;
for(i=1;i<len;i++)
{
max = inf;
for(j=0;j<=i;j++)
if(data[i]>data[j]&&max<dp[j])
max=dp[j];
dp[i]=max+1;
if(res<dp[i])
res = dp[i];
}
printf("%d\n",res);
return 0;
}

㈦ 什麼是dp演算法

DP演算法是解決多階段決策過程最優化問題的一種常用方法。
多階段決策過程（multistep decision process）是指這樣一類特殊的活動過程，過程可以按時間順序分解成若干個相互聯系的階段，在每一個階段都需要做出決策，全部過程的決策是一個決策序列。動態規劃（dynamic programming）演算法是解決多階段決策過程最優化問題的一種常用方法，難度比較大，技巧性也很強。利用動態規劃演算法，可以優雅而高效地解決很多貪婪演算法或分治演算法不能解決的問題。
動態規劃演算法的基本思想是：將待求解的問題分解成若干個相互聯系的子問題，先求解子問題，然後從這些子問題的解得到原問題的解；對於重復出現的子問題，只在第一次遇到的時候對它進行求解，並把答案保存起來，讓以後再次遇到時直接引用答案，不必重新求解。動態規劃演算法將問題的解決方案視為一系列決策的結果，與貪婪演算法不同的是，在貪婪演算法中，每採用一次貪婪准則，便做出一個不可撤回的決策；而在動態規劃演算法中，還要考察每個最優決策序列中是否包含一個最優決策子序列，即問題是否具有最優子結構性質。

㈧ C語言編程題中的DP題 是什麼類型題

DP就是動態規劃（Dynamic Programming)。

1，什麼是動態規劃（DP）？

非常重要！，不要認為概念不重要，理解的深刻，你才知道對於什麼樣的問題去考慮有沒有動態規劃的方法，以及如何去使用動態規劃。

1）動態規劃是運籌學中用於求解決策過程中的最優化數學方法。 當然，我們在這里關注的是作為一種演算法設計技術，作為一種使用多階段決策過程最優的通用方法。

它是應用數學中用於解決某類最優化問題的重要工具。

2）如果問題是由交疊的子問題所構成，我們就可以用動態規劃技術來解決它，一般來說，這樣的子問題出現在對給定問題求解的遞推關系中，這個遞推關系包含了相

同問題的更小子問題的解。動態規劃法建議，與其對交疊子問題一次又一次的求解，不如把每個較小子問題只求解一次並把結果記錄在表中（動態規劃也是空間換時間

的），這樣就可以從表中得到原始問題的解。

關鍵詞：

它往往是解決最優化問題滴

問題可以表現為多階段決策（去網上查查什麼是多階段決策！）
交疊子問題：什麼是交疊子問題，最有子結構性質。

動態規劃的思想是什麼：記憶，空間換時間，不重復求解，由交疊子問題從較小問題解逐步決策，構造較大問題的解。

一個最簡單的DP問題就是斐波拉切數列。f(n) = f(n-1) + f(n-2)
如果採用遞歸的方法計算，復雜度很高的。
還有一個問題就是矩陣的連乘問題， 計算最少的乘法次數，這些都是經典的DP問題。

㈨ 編程中的 DP是什麼意思 比如數位DP 什麼的

dp表示dynamic programing，這里programing不是編程的意思，意為規劃

dp就是動態規劃，本來是運籌學裡面的一種技術，現在多用在編程裡面。特別是信息學競賽和acm競賽

㈩ dp演算法是什麼呢

dp演算法就是動態規劃，是運籌學的一個分支，是求解決策過程最優化的過程。

動態規劃方法一般用來求解最優化問題。這類問題可以有很多可行解，每個解都有一個值，我們希望找到具有最優值的解，我們稱這樣的解為問題的一個最優解，而不是最優解，因為可能有多個解都達到最優值。

動態規劃的演算法設計

1、找出最優解的性質，並描述其結構特徵。

2、遞歸定義最優值。

3、以自底向上的方式計算最優值。

4、根據計算最優值時得到的信息構造出最優解。