# DP + HashMap => Another Angle to See the Problem

• 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);
}
}``````

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