2915. 和為目標(biāo)值的最長(zhǎng)子序列的長(zhǎng)度 - 力扣（LeetCode）

給你一個(gè)下標(biāo)從?0?開(kāi)始的整數(shù)數(shù)組?nums?和一個(gè)整數(shù)?target?。返回和為?target?的?nums?子序列中，子序列?長(zhǎng)度的最大值?。如果不存在和為?target?的子序列，返回?-1?。子序列?指的是從原數(shù)組中刪除一些或者不刪除任何元素后，剩余元素保持原來(lái)的順序構(gòu)成的數(shù)組。

（一）回溯?

• f(i,j) 表示在物品集 nums 的前 i 個(gè)選取物品，使得裝滿(mǎn)容量為 j 的背包有最多個(gè)物品
• 也就是f(i,j) 表示在數(shù)組 nums 的前 i 個(gè)的選取元素，使得這些元素之和等于 j 的 最長(zhǎng)子序列長(zhǎng)度
• 

class Solution {
public:
    // 遞歸搜索
    int lengthOfLongestSubsequence(vector<int>& nums, int target) {
        int n = nums.size();
        function<int(int,int)>dfs=[&](int i,int s) -> int {
            if(i<0) { 
                if(s==0) return 0;
                else return INT_MIN;
            }
            return max(dfs(i-1,s),dfs(i-1,s-nums[i])+1);
        };
        int ans = dfs(n-1,target);
        return ans<0?-1:ans;
    }
};

（二） 遞歸搜索 + 保存計(jì)算結(jié)果 = 記憶化搜索

class Solution {
public:
    // 記憶化遞歸搜索
    int lengthOfLongestSubsequence(vector<int>& nums, int target) {
        int n = nums.size();
        vector<vector<int>> memo(n,vector<int>(target+1,-1));
        function<int(int,int)>dfs=[&](int i,int s) -> int {
            if(i<0) { 
                if(s==0) return 0;
                else return INT_MIN;
            }
            int& res = memo[i][s];
            if(res != -1) return res;
            if (s < nums[i]) return res = dfs(i-1,s);
            return res = max(dfs(i-1,s),dfs(i-1,s-nums[i])+1);
        };
        int ans = dfs(n-1,target);
        return ans<0?-1:ans;
    }
};

class Solution {
public:
    // 記憶化遞歸搜索
    int lengthOfLongestSubsequence(vector<int>& nums, int target) {
        int n = nums.size();
        vector<vector<int>> memo(n+1,vector<int>(target+1,-1));
        function<int(int,int)>dfs=[&](int i,int s) -> int {
            if(i<0) { 
                if(s==0) return 0;
                else return INT_MIN;
            }
            int& res = memo[i+1][s];
            if(res != -1) return res;

            // 不選
            int& x = memo[i][s];
            if(x == -1) x=dfs(i-1,s);
            if (s < nums[i]) return res=x;

            // 選
            int& y = memo[i][s-nums[i]];
            if(y == -1) y=dfs(i-1,s-nums[i]);
            return res = max(x,y+1);
        };
        int ans = dfs(n-1,target);
        return ans<0?-1:ans;
    }
};

（三）1:1 翻譯成遞推

class Solution {
public:
    // 遞推
    int lengthOfLongestSubsequence(vector<int>& nums, int target) {
        int n = nums.size();
        vector<vector<int>> f(n+1,vector<int>(target+1,INT_MIN));
        f[0][0]=0;
        for(int i=0;i<nums.size();i++) {
            for(int j=0;j<=target;j++) {
                // if(j>=nums[i]) f[i+1][j] = max(f[i][j],f[i][j-nums[i]]+1);
                // else f[i+1][j] = f[i][j];
                f[i+1][j] = f[i][j];
                if(j>=nums[i]) f[i+1][j] = max(f[i][j],f[i][j-nums[i]]+1);
            }
        }
        int ans = f[n][target];
        return ans<0?-1:ans;
    }
};

進(jìn)一步優(yōu)化:

class Solution {
public: 
    // 遞推 + 優(yōu)化
    int lengthOfLongestSubsequence(vector<int>& nums, int target) {
        int n = nums.size();
        vector<vector<int>> f(n+1,vector<int>(target+1,INT_MIN));
        int sum=0;
        for(int i=0;i<nums.size();i++) {
            f[i][0]=0;
            sum=min(sum+nums[i],target);
            for(int j=1;j<=sum;j++) {
                f[i+1][j] = f[i][j];
                if(j>=nums[i]) f[i+1][j] = max(f[i][j],f[i][j-nums[i]]+1);
            }
        }
        int ans = f[n][target];
        return ans<0?-1:ans;
    }
};

>>空間優(yōu)化

• 1、二維數(shù)組空間優(yōu)化

class Solution {
public:
    // 二維空間優(yōu)化
    int lengthOfLongestSubsequence(vector<int>& nums, int target) {
        int n = nums.size();
        vector<vector<int>> dp(2,vector<int>(target+1,INT_MIN));
        int sum=0;
        for(int i=0;i<n;i++) {
            dp[i%2][0]=0;
            sum=min(sum+nums[i],target);
            for(int j=1;j<=sum;j++) {
                if(j >= nums[i]) dp[(i+1)%2][j] = max(dp[i%2][j],dp[i%2][j-nums[i]]+1);
                else dp[(i+1)%2][j] = dp[i%2][j];
            }
        }
        int ans = dp[n%2][target];
        return ans<0?-1:ans;
    }
};

• 2.一維空間優(yōu)化

class Solution {
public:
    // 一維空間優(yōu)化
    int lengthOfLongestSubsequence(vector<int>& nums, int target) {
        int n = nums.size();
        vector<int> dp(target+1,INT_MIN);
        dp[0]=0;
        int sum=0;
        for(int i=0;i<n;i++) {
            sum=min(sum+nums[i],target);
            for(int j=sum;j>=nums[i];j--) {
                dp[j] = max(dp[j],dp[j-nums[i]]+1);
            }
        }
        int ans = dp[target];
        return ans<0?-1:ans;
    }
};

內(nèi)容總結(jié)來(lái)自B站這位up主（Horn_JoJo）的視頻簡(jiǎn)介：（總結(jié)得超棒！?。。?/strong>