您好,登錄后才能下訂單哦!
這篇“C++動(dòng)態(tài)規(guī)劃算法如何使用”文章的知識(shí)點(diǎn)大部分人都不太理解,所以小編給大家總結(jié)了以下內(nèi)容,內(nèi)容詳細(xì),步驟清晰,具有一定的借鑒價(jià)值,希望大家閱讀完這篇文章能有所收獲,下面我們一起來看看這篇“C++動(dòng)態(tài)規(guī)劃算法如何使用”文章吧。
題目描述:
大家都知道斐波那契數(shù)列,現(xiàn)在要求輸入一個(gè)正整數(shù) n ,請(qǐng)你輸出斐波那契數(shù)列的第 n 項(xiàng)。
解題思路:
1.遞歸
2.動(dòng)態(tài)規(guī)劃
狀態(tài):F(n)
狀態(tài)遞推:F(n)=F(n-1)+F(n-2)
初始值:F(1)=F(2)=1
返回結(jié)果:F(N)
代碼實(shí)現(xiàn):
法一:遞歸(效率低):
class Solution{public: int Fibonacci(int n) { // 初始值 if (n <= 0) { return 0; } if (n == 1 || n == 2) { return 1; } // F(n)=F(n-1)+F(n-2) return Fibonacci(n - 2) + Fibonacci(n - 1); }};
法二:動(dòng)態(tài)規(guī)劃
class Solution { public: int Fibonacci(int n) { if(n==1 || n==2) return 1; int fn; int fn1 = 1, fn2 = 1; for(int i = 2; i < n; i++) { fn = fn1 + fn2; fn1 = fn2; fn2 = fn; } return fn; /*上述解法的空間復(fù)雜度為O(n) 其實(shí)F(n)只與它相鄰的前兩項(xiàng)有關(guān), 所以沒有必要保存所有子問題的解 只需要保存兩個(gè)子問題的解就可以 下面方法的空間復(fù)雜度將為O(1)*/ if(n==1 || n==2) return 1; int* F = new int[n]; //初始狀態(tài) F[0] = 1; F[1] = 1; for(int i = 2; i < n; i++) { F[i] = F[i-1] + F[i-2]; } return F[n-1]; } };
題目描述:
給定一個(gè)字符串s和一組單詞dict,判斷s是否可以用空格分割成一個(gè)單詞序列,使得單詞序列中所有的單詞都是dict中的單詞(序列可以包含一個(gè)或多個(gè)單詞)。
例如:
給定s=“nowcode”;
dict=[“now”, “code”].
返回true,因?yàn)?quot;nowcode"可以被分割成"now code".
解題思路:
狀態(tài):
子狀態(tài):前1,2,3,…,n個(gè)字符能否根據(jù)詞典中的詞被成功分詞
F(i): 前i個(gè)字符能否根據(jù)詞典中的詞被成功分詞
狀態(tài)遞推:
F(i): true{j <i && F(j) && substr[j+1,i]能在詞典中找到} OR false 在j小于i中,只要能找到一個(gè)F(j)為true,并且從j+1到i之間的字符能在詞典 中找到,則F(i)為true
初始值:
對(duì)于初始值無法確定的,可以引入一個(gè)不代表實(shí)際意義的空狀態(tài),作為狀態(tài)的起始 空狀態(tài)的值需要保證狀態(tài)遞推可以正確且順利的進(jìn)行,到底取什么值可以通過簡單的例子進(jìn)行驗(yàn)證 F(0) = true
返回結(jié)果:F(n)
代碼實(shí)現(xiàn):
class Solution { public: bool wordBreak(string s, unordered_set<string> &dict) { int len = s.size(); vector<bool> F(len+1, false); F[0] = true; for(int i = 1; i <= len; i++) { //F[8]的狀態(tài):7<8 && F[7] && [8,8] //F[8]的狀態(tài):6<8 && F[6] && [7,8] for(int j = i-1; j >= 0; j--) { if(F[j] && dict.find(s.substr(j,i-j)) != dict.end()) { F[i] = true; break; } } } return F[len]; } };
題目描述:
給出一個(gè)三角形,計(jì)算從三角形頂部到底部的最小路徑和,每一步都可以移動(dòng)到下面一行相鄰的數(shù)字
例如,給出的三角形如下:
[[20],[30,40],[60,50,70],[40,10,80,30]]
解題思路:
狀態(tài):子狀態(tài):從(0,0)到(1,0),(1,1),(2,0),…(n,n)的最短路徑和 F(i,j): 從(0,0)到(i,j)的最短路徑和
狀態(tài)遞推: F(i,j) = min( F(i-1, j-1), F(i-1, j)) + triangle[i][j]
初始值: F(0,0) = triangle[0][0]返回結(jié)果: min(F(n-1, i))
代碼實(shí)現(xiàn):
class Solution { public: int minimumTotal(vector<vector<int> > &triangle) { if(triangle.empty()) return 0; int row = triangle.size(); vector<vector<int> > minSum(triangle); for(int i = 1; i < row; i++) { for(int j = 0; j <= i; j++) { if(j == 0) minSum[i][j] = minSum[i-1][j] + triangle[i][j]; else if(j == i) minSum[i][j] = minSum[i-1][j-1] + triangle[i][j]; else minSum[i][j] = min(minSum[i-1][j], minSum[i-1][j-1]) + triangle[i][j]; } } int result = minSum[row-1][0]; for(int i = 1; i < triangle.size(); i++) { result = min(result, minSum[row-1][i]); } return result; } };
題目描述:
一個(gè)機(jī)器人在m×n大小的地圖的左上角(起點(diǎn))。 機(jī)器人每次可以向下或向右移動(dòng)。機(jī)器人要到達(dá)地圖的右下角(終點(diǎn))。 可以有多少種不同的路徑從起點(diǎn)走到終點(diǎn)?
解題思路:
狀態(tài):子狀態(tài):從(0,0)到達(dá)(1,0),(1,1),(2,1),…(m-1,n-1)的路徑數(shù) F(i,j): 從(0,0)到達(dá)F(i,j)的路徑數(shù)
狀態(tài)遞推: F(i,j) = F(i-1,j) + F(i,j-1)
初始化: 特殊情況:第0行和第0列 F(0,i) = 1 F(i,0) = 1
返回結(jié)果: F(m-1,n-1)
代碼實(shí)現(xiàn):
class Solution { public: /** * * @param m int整型 * @param n int整型 * @return int整型 */ int uniquePaths(int m, int n) { // write code here vector<vector<int> > ret(m, vector<int>(n,1)); for(int i = 1; i < m; i++) { for(int j = 1; j < n; j++) { ret[i][j] = ret[i-1][j] + ret[i][j-1]; } } return ret[m-1][n-1]; } };
題目描述:
給定一個(gè)由非負(fù)整數(shù)填充的m x n的二維數(shù)組,現(xiàn)在要從二維數(shù)組的左上角走到右下角,請(qǐng)找出路徑上的所有數(shù)字之和最小的路徑。 注意:你每次只能向下或向右移動(dòng)。
解題思路:
狀態(tài):子狀態(tài):從(0,0)到達(dá)(1,0),(1,1),(2,1),…(m-1,n-1)的最短路徑 F(i,j): 從(0,0)到達(dá)F(i,j)的最短路徑。
狀態(tài)遞推: F(i,j) = min{F(i-1,j) , F(i,j-1)} + (i,j)
初始化: F(0,0) = (0,0) 特殊情況:第0行和第0列 F(0,i) = F(0,i-1) + (0,i) F(i,0) = F(i-1,0) + (i,0)
返回結(jié)果: F(m-1,n-1)
代碼實(shí)現(xiàn):
class Solution { public: /** * * @param grid int整型vector<vector<>> * @return int整型 */ int minPathSum(vector<vector<int> >& grid) { // write code here if(grid.size() == 0 || grid[0].size() == 0) return 0; int M = grid.size(); int N = grid[0].size(); vector<vector<int> > ret(M, vector<int>(N,0)); ret[0][0] = grid[0][0]; for(int i = 1; i < N; i++) { ret[0][i] = ret[0][i-1] + grid[0][i]; } for(int i = 1; i < M; i++) { ret[i][0] = ret[i-1][0] + grid[i][0]; } for(int i = 1; i < M; i++) { for(int j = 1; j < N; j++) { ret[i][j] = min(ret[i-1][j],ret[i][j-1]) + grid[i][j]; } } return ret[M-1][N-1]; } };
以上就是關(guān)于“C++動(dòng)態(tài)規(guī)劃算法如何使用”這篇文章的內(nèi)容,相信大家都有了一定的了解,希望小編分享的內(nèi)容對(duì)大家有幫助,若想了解更多相關(guān)的知識(shí)內(nèi)容,請(qǐng)關(guān)注億速云行業(yè)資訊頻道。
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng),如果涉及侵權(quán)請(qǐng)聯(lián)系站長郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。