动态规划

最长上升子序列(一)

牛客链接：NC163 最长上升子序列(一)

定义长度为n的ans数组，用以保存以arr[i]结尾的最长严格上升子序列的长度。在每次获得最长序列的时候进行比较从而得到最终结果。结果满足复杂度要求。

class Solution {
   
public:
    /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * 给定数组的最长严格上升子序列的长度。 * @param arr int整型vector 给定的数组 * @return int整型 */
    int LIS(vector<int>& arr) {
   
        // write code here
        if(arr.size()==0)
            return 0;
        int res = 0;
        vector<int> ans(arr.size(),1);
        for(int i = 1; i < arr.size();++i){
   
            for(int j =0; j<i; ++j){
   
                if(arr[i]>arr[j])
                    {
   
                        ans[i] = max(ans[i],ans[j]+1);
                    }
            }
            res = max(ans[i] ,res);
        }
        return res;
    }
};

最长上升子序列(二)

牛客链接：NC164 最长上升子序列(二)

和上题目目的相同，只是更严格的要求了时间和空间复杂度。这里使用动态规划+二分的思路。
arr[i]用来存储尽可能小的值，因为小的值在后续中，更可能寻找到大的值从而使得长度增加。
遍历每个a[ i ]，如果严格大于arr的最后一个数，则加入arr；
否则，找到找到大于等于他的最小的一个数，进行替换。
最终获得的arr的长度就是答案。

//实现1：手写二分
class Solution {
   
public:
    /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * 该数组最长严格上升子序列的长度 * @param a int整型vector 给定的数组 * @return int整型 */
    int LIS(vector<int>& a) {
   
        // write code here
        int n=a.size();
        if(n==0)
            return 0;
        vector<int> arr;
        arr.push_back(a[0]);
        for(int i =1;i<n;++i){
   
            if(a[i]>arr.back()){
   
                arr.push_back(a[i]);
            }
            else{
   
                int l=0, r = arr.size()-1,mid;
                while(l<r){
       	//寻找>=的位置 也可以直接使用lower_bound() 替代
                    mid = (l+r)>>1;
                    if(arr[mid]>=a[i])
                        r = mid;
                    else
                        l = mid+1;
                }
                arr[l] = a[i];  //更新长度为l的子序列的最小值
            }
        }
        return arr.size();
    }
};


//实现2:调用函数
class Solution {
   
public:
    /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * 该数组最长严格上升子序列的长度 * @param a int整型vector 给定的数组 * @return int整型 */
    int LIS(vector<int>& a) {
   
        // write code here
        vector<int> arr;
        for(int i : a){
   
            vector<int>::iterator it = lower_bound(arr.begin(),arr.end(),i);
            if(it == arr.end())
                arr.push_back(i);
            else
                *it = i;
        }
        return arr.size();
    }
};

最长公共子序列(一)

牛客链接：NC165 最长公共子序列(一)


题解一：满足要求1

定义ans[][]二维数组，其中ans[i][j] 表示s1中第i个字符和s2中第j个字符为结尾的最长公共子序列。如果 s1[i-1]==s2[j-1]，结果则为ans[i-1][j-1]+1，否则最大值在ans[i-1][j], ans[i][j-1]中产生。

class Solution {
   
public:
    /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * s1和s2最长公共子序列的长度 * @param s1 string字符串 * @param s2 string字符串 * @return int整型 */
    int LCS(string s1, string s2) {
   
        // write code here
        vector<vector<int>> ans(s1.size()+1,vector<int>(s2.size()+1,0));
        for(int i = 1;i<=s1.size();++i)
            for(int j = 1; j<=s2.size(); ++j)
            {
   
                if(s1[i-1] == s2[j-1])
                    ans[i][j] = ans[i-1][j-1] + 1;
                else 
                    ans[i][j] = max(ans[i-1][j], ans[i][j-1]);
                    
            }
        return ans[s1.size()][s2.size()];
    }
};

解法2：进阶版

解法1中，建立的arr数组，其实每次都只是用了当前行和之前一行的数据，因此可以使用两个一维数组代替。
b数组用于保存上次的结果，a数组用于计算当前行的结果。

class Solution {
   
public:
    /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * s1和s2最长公共子序列的长度 * @param s1 string字符串 * @param s2 string字符串 * @return int整型 */
    int LCS(string s1, string s2) {
   
        // write code here
        int n = min(s1.size(),s2.size());
        vector<int> a(n+1,0);
        vector<int> b(n+1,0);

        if(s1.size()<s2.size())
            swap(s1,s2);

        for(int i = 1; i<=s1.size();++i){
   
            for(int j = 1; j<=s2.size(); ++j)
            {
   
               if(s1[i-1] == s2[j-1])
                   a[j] = b[j-1] + 1;
                else
                    a[j] = max(a[j-1],b[j]);
            }
            swap(a, b);           //交换a,b 
            a =  vector<int>(n+1,0); //初始化a为全0的数组
        }
        return b[n];
    }
};

填充数组

牛客链接:NC173 填充数组

对于数组中的每一段0，都可以是一个子问题：填充数为i，填充范围为j个数。
因此这里建立一个dp[i][j]二维数组，其中i表示待填充数的个数，j表示待填充位置的候选范围个数。

  1. 待填充个数为0时，dp[0][j] = 0；
  2. 候选范围为0时候，dp[i][0] = 0;
  3. 待填充个数为1时，dp[1][j] = j；
  4. 对于dp[i][j]，可以拓展为与dp[i-1][j]和dp[i][j]的关系。 dp[i][j] = dp[i-1][j] + dp[i][j-1]：当前第i个数填充j个范围中最大数时，候选方案为 dp[i-1][j] ，当第i个数填充（0 - j-1）范围的时候，结果就是dp[i][j-1]； 
class Solution {
   
public:
    /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param a int整型vector * @param k int整型 * @return int整型 */
    const int MOD = 1e9+7;
    int FillArray(vector<int>& a, int k) {
   
        // write code here 
        int n = a.size();
        vector<vector<int>> dp(n+1,vector<int>(k+1,0));
        for(int i = 0; i <= k; ++i){
   
            dp[1][i] = i; 
        }
        for(int  i =2;i<=n; ++i){
   
            for(int j = 1;j <=k; ++j){
   
                dp[i][j] = (dp[i][j-1] + dp[i-1][j])%MOD; 
            }
        }
        
        int i=0;
        long long res = 1;
        while(i<n){
       //计算每一段的方案数，累乘 
            while(i<n&&a[i]!=0){
   
                i++;
            }
            if(i==n)
                break;
            int left=i;				  //左区间 左端第一个为0的数
            int low=i>0?a[i-1]:1;     //候选的范围的低值
            while(i<n&&a[i]==0){
   
                i++;
            }
            int right=i;		 	//右区间 右端最后一个为0的数
            int high=i<n?a[i]:k;    //候选的范围的高值 当为n的时候，表示最后一段到结尾的为0，就要考虑极限值。
            res=(res*dp[right-left][high-low+1])%MOD;          //累乘
        }
        return res;
    }
};

打家劫舍(一)

牛客链接:NC176 打家劫舍(一)

解法1

定义数组dp，其中dp[i]表示一共有i家能够偷到的最大值金额。其中dp[i] = max(dp[i-1],dp[i-2]+nums[i-1]); 一共有i家能够偷到的最大金额需要考虑有i-1家和i-2家的情况。这两种情况有可能相同，但是i-2家的时候可以选择投第i家，i-1家不一定，有可能i-1家被偷了，那么第i家就不能偷了。

class Solution {
   
public:
    /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param nums int整型vector * @return int整型 */
    int rob(vector<int>& nums) {
   
        // write code here
        vector<int> dp(nums.size()+1,0);
        dp[1] = nums[0];
        for(int i =2;i<=nums.size();++i){
   
            dp[i] = max(dp[i-1],dp[i-2]+nums[i-1]);
        }
        return dp[nums.size()];
    }
};

解法2

定义二维数组dp，其中dp[i][0]表示第i家不偷的情况能够获得的最大值，dp[i][1]表示偷第i家能够获得的最大值。其中dp[i][0] = max(dp[i-1][0],dp[i-1][1])，dp[i][1] = dp[i-1][0] + nums[i];

class Solution {
   
public:
    /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param nums int整型vector * @return int整型 */
    int rob(vector<int>& nums) {
   
        // write code here
        vector<vector<int>> dp(nums.size(),vector<int>(2,0));
        dp[0][0] = 0;
        dp[0][1] = nums[0];
        for(int i =1;i<nums.size(); ++i){
   
            dp[i][0] = max(dp[i-1][0],dp[i-1][1]);  //不偷这家
            dp[i][1] = dp[i-1][0] + nums[i];        //偷这家
        }
        return max(dp[nums.size()-1][0],dp[nums.size()-1][1]);
    }
};

优化：上述方法2每次考虑当前住户的时候其实只用到之前的一家的信息，所以可以使用两个变量来替代数组。

class Solution {
   
public:
    /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param nums int整型vector * @return int整型 */
    int rob(vector<int>& nums) {
   
        // write code here
        int last_notsteal = 0;
        int last_steal = nums[0];
        int temp;
        for(int i =1;i<nums.size(); ++i){
   
            temp = last_notsteal;
            last_notsteal = max(last_notsteal,last_steal);  //不偷这家
            last_steal = temp + nums[i];        //偷这家
        }
        return max(last_notsteal,last_steal);
    }
};

打家劫舍(二)

牛客链接：NC177 打家劫舍(二)

解法1

和（一）中一样，这里多了一个考虑环形的设计，导致我们需要考虑两种情况：

  1. 第一家偷，那就不能考虑最后一家，最后一家只能不偷，那么结果就是dp[n-1]；
  2. 第一家不偷，那么初始化dp[1] = 0，最终结果为dp[n]，取决于第n家偷不偷产生的最大值。 
class Solution {
   
public:
    /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param nums int整型vector * @return int整型 */
    int rob(vector<int>& nums) {
   
        // write code here
        vector<int> dp(nums.size()+1,0);
        dp[1] = nums[0];
        for(int i =2;i<nums.size();++i){
   
            dp[i] = max(dp[i-1],dp[i-2]+nums[i-1]);
        }
        int ans = dp[nums.size()-1];
        dp[1] = 0;
        for(int i =2;i<=nums.size();++i){
   
            dp[i] = max(dp[i-1],dp[i-2]+nums[i-1]);
        }
        ans = max(ans,dp[nums.size()]);
        return ans;
    }
};

解法2

同(一)，使用两个变量来保存偷与不偷，考虑不同的初始化。只要第一家和最后一家不同时考虑。 考虑第一家到第n-1家和第2家到第n家两种情况最大值，必定不会出现头尾都偷的情况。

class Solution {
   
public:
    /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param nums int整型vector * @return int整型 */
    int rob(vector<int>& nums) {
   
        // write code here
        int last_notsteal = 0;
        int last_steal = nums[0];
        int temp;
        for(int i =1;i<nums.size()-1; ++i){
   
            temp = last_notsteal;
            last_notsteal = max(last_notsteal,last_steal);  //不偷这家
            last_steal = temp + nums[i];        //偷这家
        }
        
        int res = max(last_notsteal,last_steal);
        last_notsteal = 0;
        last_steal = nums[1];
        for(int i =2;i<nums.size(); ++i){
   
            temp = last_notsteal;
            last_notsteal = max(last_notsteal,last_steal);  //不偷这家
            last_steal = temp + nums[i];        //偷这家
        }
        res = max(res,max(last_notsteal,last_steal));
        
        return res;
    }
};

打家劫舍(三)

牛客链接：NC178 打家劫舍(三)

解法1：DFS

会超时。每次递归每个树的结点，考虑选择偷与不偷当前结点。最终取最大值就是结果，

/** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * }; */
class Solution {
   
public:
    /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param root TreeNode类 * @return int整型 */
    int dfs(TreeNode* r,bool pick = true){
    // 当前是否可选
        if(r == NULL)return 0;
        // 当前不选
        int ans = dfs(r->left) + dfs(r->right);
        // 选择当前
        if(pick){
   
            ans = max(ans, r->val + dfs(r->left,false) + dfs(r->right,false));
        }
        return ans;
    }
    
    int rob(TreeNode* root) {
   
        return dfs(root);
    }
};

解法2

利用深度遍历从最后一层到根判断是否偷该结点。
当偷该节点的时候，两个子节点都不偷。
当不偷该节点的时候，有四种可能：

  1. 两个根节点都不偷
  2. 两个根节点都偷
  3. 偷左节点，不偷右节点
  4. 偷右节点，不偷左节点 
/** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * }; */
class Solution {
   
public:
    /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param root TreeNode类 * @return int整型 */
    pair<int, int> dfs(TreeNode* root){
         //其中first表示不偷，second表示偷
        if(root == nullptr)
            return {
   0,0};
        pair<int, int> left,right;
        left = dfs(root->left);
        right = dfs(root->right);
        //不偷的情况有四种
        int no_steal = max(left.second+right.second,max(left.first+right.first,\
        				max(left.second+right.first,left.first+right.second)));
        int steal = left.first + right.first + root->val;
        return {
   no_steal,steal};
    }
    int rob(TreeNode* root) {
   
        // write code here
        pair<int, int> ans = dfs(root);
        return max(ans.first, ans.second);
    }
};

目标和

牛客链接:NC243 目标和

解法1：DFS

对于数组中每个元素都进行正负号的判断，最终数组到达尾部，且target为0时就是一个候选选项。

class Solution {
   
public:
    /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param nums int整型vector * @param target int整型 * @return int整型 */
    int dfs(vector<int>& nums, int target){
   
         if(target == 0 && nums.size() == 0)
            return 1;
        if(nums.size() == 0)
            return 0;
        int ans = 0;
        vector<int> temp(nums.begin()+1,nums.end());
        ans += dfs(temp,  target+nums[0]);
        ans += dfs(temp,  target-nums[0]);
        return ans;
    }
    
    int findTargetSumWays(vector<int>& nums, int target) {
   
        // write code here
        if(nums.size() == 0)
            return 0;
        int ans = 0;
        vector<int> temp(nums.begin()+1,nums.end());
        ans += dfs(temp,  target+nums[0]);
        ans += dfs(temp,  target-nums[0]);
        return ans;
        
    }
};

解法2：动态规划

我们定义整个数组分为两部分一部分为加上去的总值a，一部分为减去的总值b；其中a+b=sum，a-b = target； 所以2*a = sum+target（偶数）;
题目就变成了从n个元素数组中选择n个数和为a的次数，这就形成了01完全背包问题。

class Solution {
   
public:
    /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param nums int整型vector * @param target int整型 * @return int整型 */
    int findTargetSumWays(vector<int>& nums, int target) {
   
        // write code here
        if(nums.size() == 0)
            return 0;
        int sum = 0;
        for(auto num: nums)
            sum+=num;
        if((sum+target)%2==1)
            return 0;
        
        int v = (sum+target)/2;
        vector<vector<int>> dp(nums.size()+1,vector<int>(v+1,0));
        dp[0][0] = 1;
        for(int i =1; i<=nums.size(); ++i){
   
            for(int j =0; j<=v; ++j){
   
                dp[i][j] = dp[i-1][j];
                if(j>=nums[i-1])
                    dp[i][j] +=  dp[i-1][j-nums[i-1]];
            }
        }
        return dp[nums.size()][v];
    }
};

每行元素之和上一行有关，可使用滑动数组的方式去掉第一个维度

class Solution {
   
public:
    /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param nums int整型vector * @param target int整型 * @return int整型 */
    int findTargetSumWays(vector<int>& nums, int target) {
   
        // write code here
        if(nums.size() == 0)
            return 0;
        int sum = 0;
        for(auto num: nums)
            sum+=num;
        if((sum+target)%2==1)
            return 0;
        
        int v = (sum+target)/2;
        vector<int> dp(v+1,0);
        dp[0]= 1;
        
        for(int i =0; i<nums.size(); ++i){
   
            for(int j = v; j>=nums[i]; --j){
   
                    dp[j] +=  dp[j-nums[i]];
            }
        }
        
        return dp[v];
    }
};