C# dp


  • 0
    H
    public int FindTargetSumWays(int[] nums, int S) {
            Dictionary<int, int> d = new Dictionary<int, int>();
            d[0] = 1;
            Action<Dictionary<int, int>, int, int> incr = new Action<Dictionary<int, int>, int, int> ((dict, k, v) => { dict[k] = dict.ContainsKey(k) ? dict[k] + v : v; });
            for(int i = 0; i < nums.Length; i++) {
                Dictionary<int, int> d2 = new Dictionary<int, int>();
                foreach(int k in d.Keys) {
                    incr(d2, k + nums[i], d[k]);
                    incr(d2, k - nums[i], d[k]);
                }
                d = d2;
            }
            
            return d.ContainsKey(S) ? d[S] : 0;
        }
    

Log in to reply
 

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