線性DP

53. 最大子數組和

思路

code?

int maxSubArray(vector<int>& nums) {//res:最后所有狀態的最終Max結果//lat:當前f[i]狀態的Maxint res = INT_MIN, last = 0;for (int i = 0; i < nums.size(); i++){//當前f[i]狀態最大值(使用下面的狀態轉移方程得出)//f[i] = max( nums[i] , f[i - 1] + nums[i] )int now = max(last, 0) + nums[i];/*最終是所有狀態取一個max所以此處保存前后兩個狀態相互比較的最終結果*/res = max(now, res);//更新最后,當為i時候,f[i]的最大值,即lastlast = now;}return res;}

120. 三角形最小路徑和

思路

code

//自上而下 int minimumTotal(vector<vector<int>>& nums) {int n = nums.size();vector<vector<long long>>f(n, vector<long long>(n));f[0][0] = nums[0][0];for(int i = 1; i < n ;i++)for (int j = 0; j <= i; j++){f[i][j] = INT_MAX;//邊界判斷if (j > 0) f[i][j] = min(f[i][j], f[i - 1][j - 1] + nums[i][j]);if (j < i) f[i][j] = min(f[i][j], f[i - 1][j] + nums[i][j]);}long long res = INT_MAX;for (int i = 0; i < n; i++) res = min(res, f[n - 1][i]);return res;}//自下而上不需要考慮邊界問題 int minimumTotal(vector<vector<int>>& f) {// f.size()-2 是因為最后一行不需要計算for (int i = f.size() - 2; i >= 0; i--)for (int j = 0; j <= i; j++)f[i][j] += min(f[i + 1][j], f[i + 1][j + 1]);return f[0][0]; }

63. 不同路徑 II

思路

code

class Solution { public:int uniquePathsWithObstacles(vector<vector<int>>& o) {int n = o.size();if (!n) return 0;int m = o[0].size();vector<vector<int>> f(n, vector<int>(m));for (int i = 0; i < n; i ++ )for (int j = 0; j < m; j ++ )//判斷如果不為障礙物的話才執行if (!o[i][j]) {if (!i && !j) f[i][j] = 1;//特判左上角開始位置else {//如果不是第一行if (i) f[i][j] += f[i - 1][j];//如果不是第一列if (j) f[i][j] += f[i][j - 1];}}return f[n - 1][m - 1];} };

121. 買賣股票的最佳時機

思路

此題目為一個動態規劃的過程，目標是需要求得最大的利潤。

1.最大利潤（分析）把整個區間劃分為若干份，計算出區間每一個的局部最大值，然后再比較出整體區間的最大值即為答案。

max(max[0],max[1],max[2],max[---])

2.當前最利潤為：當前的元素prices[i] -? 過往區間最小的值(minp)，并且更新過往最大利潤res

3.最終更新最小值(minp) = min(當前最小值（即prices[i]自身）,過往區間最小值(minp))?

4.總結 ：線性記錄 res 和 minp 始終為過往區間的(最大利潤) 與 (最小值)

code

int maxProfit(vector<int>& prices) {//res為當前最終結果int res = 0;for (int i = 0, minp = INT_MAX; i < prices.size(); i++) {//prices[i] - minp為當天最大利潤//max(res, prices[i] - minp)為截止至今日，最大利潤//res = max(res, prices[i] - minp);更新當前掃描的最大利潤res = max(res, prices[i] - minp);//更新前面最小值(當前更新位置始終為整個區間的最小值)minp = min(minp, prices[i]);}return res; }

總結

以上是生活随笔為你收集整理的leetcode(动态规划专题)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。