最長遞增子序列（一維）

子序列是可以不連續的。
，dp[i]是i位置以num[i]結尾的最長子序列長度
狀態轉移方程：

$$dp[i]=max(dp[i],dp[j]+1),j<i且滿足num[i]>num[j]$$

代碼：

memset(dp,1,sizeof(dp)) //初始化為1，因為自己本身。 for(int i=0;i<n;++i)for(int j=0;j<i;++j){if(nums[i]>nums[j])dp[i] = max(dp[i] ,dp[j]+1);}

之后遍歷一篇dp取最大的值就可以了。

最長遞增子序列（二維）

一般題目是一個二維的數據，如給信封的長和寬，問最多可以嵌套多少個信封。
思路：
可以統一將信封的長進行升序排列，如果長度一樣，就以寬度降序排列。
然后將寬度取出，在寬度中最長遞增子序列就是答案。

bool cmp(vector<int>a,vector<int>b) {a[0] == b[0]?return a[1]>b[1]:a[0]<b[0] ; }sort(nums,nums+n,cmp) vector<int>ans; for(int i =0;i<n;++i)ans.push_back(nums[i][1]); //然后將這個ans求最長遞增子序列。

最大子數組

子數組或子字符串是連續的。
，dp[i]是i位置以num[i]結尾的最大數組和
在dp[i]位置只有兩個選擇，一個是與前一個數組合并，另一個是自己新建立一個數組。
所以有狀態轉移方程：
$$dp[i]=max(dp[i?1]+nums[i],nums[i])$$

dp[0] = nums[0];//因為第一個數字只能選擇自己。 for(int i =1;i<n;++i)dp[i]=max(dp[i-1]+nums[i],nums[i]) ; //然后遍歷一邊dp數組，取最大值就是答案了。

跳躍游戲I

題意是：給一個數組nums,nums[i]是在位置i最多能向前跳躍的步數。問能否可以跳躍到最后一個位置。

思路：我們記錄在位置i能最多跳躍到的位置，將問題轉化為這最大的位置是否比最后一個位置大就好了。

int ans = 0; for(int i=0;i<n-1;++i) {ans = max(ans,i+nums[i]);if(ans<=i) //說明遇到了0，那么就無法跳了。return false;return ans>=n-1; }

跳躍游戲II

現在問的是跳到最后一個需要的最少跳躍次數。

貪心思路：我們在一個位置上最長能跳躍到的區間上，選出最大的一個跳躍步數就可以。

int end = 0; //站在索引i，最大能跳躍到end int fartest =0; //從索引[i...end]起跳，最遠到的距離。 int jump = 0; for(int i =0;i<n-1;++i) {fartest = max(fartest,i+nums[i]);if(end = i){jump ++;end = fartest ;} }

01背包

01背包的狀態轉移方程為
$$f[i][j]=max(f[i?1][j],f[i?1][j?w[i]]+v[j])$$

i代表對i件物體做決策，有兩種方式—放入背包和不放入背包。
j表示當前背包的容量。

不放入背包時:第i次決策后的最大價值和第i-1次決策時候的價值是一樣的（還是原來的那些物體，沒多沒少）。
放入背包時:第i次決策后的價值為 第i-1次決策時候的價值 加上 當前物體的價值v[j]。物體放入背包后會使背包容量變為 j ，即沒放物體之前背包的容量為j - w[i]。想想啊當前背包容量為j，而這個j是在加了w[i]之后得到的，那么i-1時候背包容量不就是j-w[i]嘛

//代碼里面將整個f初始化為0 for (int i = 1; i <= n; i++) {for (int j = V; j >= 0; j--){if (j >= w[i])//如果背包裝得下當前的物體{f[i][j] = max(f[i - 1][j], f[i - 1][j - w[i]] + v[i]);}else//如果背包裝不下當前物體{f[i][j] = f[i - 1][j];}} }

優化，只需要一維數組就好了

//代碼里面將整個f初始化為0 for (int i = 1; i <= n; i++) {for (int j = V; j >= w[i]; j--){f[j] = max(f[j], f[j - w[i]] + v[i]);} }

總結

以上是生活随笔為你收集整理的动态规划/贪心总结（一）的全部內容，希望文章能夠幫你解決所遇到的問題。

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