C# DP O(target * n) solution


  • 0
    K

    We use a DP array of length target + 1. The ith value of the array indicates the combinations to create i from the array. So the reccurance relation would then be dp[i] = sum(dp[target - arr[j]) for j = 0..Arr.Length, and (target - arr[j]) >= 0.

    public class Solution {
        public int CombinationSum4(int[] nums, int target) {
            int[] dp = new int[target + 1];
            dp[0] = 1;
            for (int i = 1; i <= target; i++) {
                for (int j = 0; j < nums.Length; j++) {
                    if (i - nums[j] >= 0) {
                        dp[i] += dp[i - nums[j]];
                    }
                }
            }
            
            return dp[target];
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.