代码随想录训练营第35天|逆序背包

46. 携带研究材料 

#include <iostream>
#include <vector>
using namespace std;
int main(){int m,n;cin>>m>>n;vector<int> weights(m,0), values(m,0),dp(n+1,0);for(int i=0; i<m; i++){cin>>weights[i];}for(int i=0; i<m; i++){cin>>values[i];}for(int j=0; j<m; j++){for(int i=n;i>=weights[j];i--){dp[i]=max(dp[i],dp[i-weights[j]]+values[j]);}}cout<<dp[n]<<endl;return 0;
}

经典的01背包问题，dp[i]表示容量为i的背包所能装载的最大价值。

状态转移方程：dp[i]=max(dp[i],dp[i-weights[j]]+values[j]);

用不同的物品刷新"滚动数组",每一个新的物品会占据空间weights[j]，并带来价值values[j]，所以得到新的价值：dp[i-weights[j]]+values[j], dp[i]累计所有可能的最大值。

另外一个细节，背包容量需要逆序遍历，这样对推过程中利用的dp[i-weights[j]]均是不考虑values[j]的最优解，也即每个物品只能使用一次。反之，如果正序遍历，大容量的dp由小容量的dp计算而来，都会计入values[j]，这样一个物品就会被使用多次，成为完全背包问题。

416. 分割等和子集

class Solution {
public:bool canPartition(vector<int>& nums) {int sum=accumulate(nums.begin(),nums.end(),0);if(sum%2==1)return false;int target=sum/2;vector<int> dp(target+1,0);for(auto& num:nums){for(int i=target; i>=num; i--){dp[i]=max(dp[i],dp[i-num]+num);}}return dp[target]==target;}
};

转化为背包问题：重量为nums的石头，放入target容量的背包中，求可放入的最大重量（价值=重量）。

5. 最长回文子串

class Solution {
public:int get_length(string& s, int left, int right){while(left>=0&&right<s.length()&&s[left]==s[right]){left--;right++;};return right-left+1-2;}string longestPalindrome(string s) {if(s.length()<2)return s;int max_len=INT_MIN,start;for(int i=0; i<s.length()-1; i++){int l1=get_length(s,i,i);int l2=get_length(s,i,i+1);if(l1>max_len){max_len=l1;start=i-(max_len-1)/2;}if(l2>max_len){max_len=l2;start=i+1-max_len/2;}}return s.substr(start,max_len);}
};

贪心解法，从中心向两边扩散，得到回文长度。遍历所有可能的中心，累计最大值。