Length of the Longest Subsequence That Sums to Target

This approach is an iterative version of the memoized recursion, often called bottom-up dynamic programming. It solves the problem by building up a solution from the smallest subproblems. This problem can be framed as a classic 0/1 Knapsack problem, where items are the numbers in nums, their 'weight' is their value, their 'value' is 1 (since we want to maximize the count), and the knapsack capacity is the target.

• Create a 2D DP table, dp[n + 1][target + 1].
• dp[i][j] will store the length of the longest subsequence using elements from nums[0...i-1] that sums to j.
• Initialize the table with a value indicating impossibility, like -1.
• Set the base case: dp[i][0] = 0 for all i from 0 to n, as a sum of 0 is always possible with an empty subsequence of length 0.
• Iterate from i = 1 to n (for each number in nums).
• Inside, iterate from j = 1 to target (for each possible sum).
• For each dp[i][j], calculate the value based on two choices for nums[i-1]:
  1. Don't include nums[i-1]: The length is dp[i-1][j].
  2. Include nums[i-1]: If j >= nums[i-1] and dp[i-1][j - nums[i-1]] is not -1, the length is 1 + dp[i-1][j - nums[i-1]].
• Set dp[i][j] to the maximum of the valid options.
• The final answer is dp[n][target].

We use a 2D array dp of size (n+1) x (target+1). dp[i][j] represents the maximum length of a subsequence using the first i numbers from nums that sums up to j. We fill this table iteratively. For each number nums[i-1], and for each possible sum j, we decide whether to include nums[i-1] in the subsequence or not. The value of dp[i][j] is determined by taking the maximum of these two choices: (1) the length without including the current number, which is dp[i-1][j], and (2) the length if we include the current number, which is 1 + dp[i-1][j - nums[i-1]]. The second choice is only possible if the target j is at least nums[i-1] and a valid subsequence existed for the subproblem dp[i-1][j - nums[i-1]].

import java.util.Arrays;
import java.util.List;

class Solution {
    public int lengthOfLongestSubsequence(List<Integer> nums, int target) {
        int n = nums.size();
        int[][] dp = new int[n + 1][target + 1];

        // Initialize dp table with -1 to indicate that a sum is not possible.
        for (int[] row : dp) {
            Arrays.fill(row, -1);
        }

        // Base case: a sum of 0 can always be achieved with an empty subsequence (length 0).
        for (int i = 0; i <= n; i++) {
            dp[i][0] = 0;
        }

        for (int i = 1; i <= n; i++) {
            int num = nums.get(i - 1);
            for (int j = 1; j <= target; j++) {
                // Option 1: Exclude the current number. The length is the same as before.
                dp[i][j] = dp[i - 1][j];

                // Option 2: Include the current number, if possible.
                if (j >= num && dp[i - 1][j - num] != -1) {
                    dp[i][j] = Math.max(dp[i][j], 1 + dp[i - 1][j - num]);
                }
            }
        }

        return dp[n][target];
    }
}