DP + HashMap => Another Angle to See the Problem


  • 0

    The first impression about problem is that it's constructed like Frog Jump, in that the previous step provides options for the next step.
    https://leetcode.com/problems/frog-jump/
    https://leetcode.com/articles/frog-jump/
    In this sense, we build a simple HashMap at each step to record the options, and the final result comes from the last step.

    public class Solution {
        public int findTargetSumWays(int[] nums, int S) {
            int n = nums.length; 
            Map<Integer, Integer>[] maps = new HashMap[n + 1]; 
            // an array of HashMaps
            for (int i = 0; i <= n; i++)
                maps[i] = new HashMap<>(); 
            maps[0].put(0, 1); 
            for (int i = 1; i <= n; i++) 
                for (int key : maps[i - 1].keySet()) {
                    int newKeyPlus = key + nums[i - 1]; 
                    int newKeyMinus = key - nums[i - 1]; 
                    // the previous step provides options for the next step. It goes 2 directions. 
                    maps[i].put(newKeyPlus, maps[i].getOrDefault(newKeyPlus, 0) + maps[i - 1].get(key)); 
                    maps[i].put(newKeyMinus, maps[i].getOrDefault(newKeyMinus, 0) + maps[i - 1].get(key)); 
                }
            // result comes from the last HashMap. 
            return maps[n].getOrDefault(S, 0); 
        }
    }

Log in to reply
 

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