venera.varbanova
BAN USERHere is a decent explanation on how to do that and why:
www_codeproject_com/Articles/15351/Implementing-a-simple-smart-pointer-in-c
(subs the _ with dots...)
import java.util.HashMap;
import java.util.HashSet;
public class Stairs {
static HashMap<Integer, HashSet<String>> memoize_map = new HashMap<Integer, HashSet<String>>();
static HashSet<String> findWaysToClimbNStairs(int n)
{
System.out.println("calling findWaysToClimbNStairs for n =" + n);
HashSet<String> strings = new HashSet<String> ();
if (n < 1) return strings;
HashSet<String> hs1 = new HashSet<String>();
hs1.add("1");
HashSet<String> hs2 = new HashSet<String>();
hs2.add("11");
hs2.add("2");
memoize_map.put(0, new HashSet<String>());
memoize_map.put(1, hs1);
memoize_map.put(2, hs2);
if (n == 1)
{
return memoize_map.get(1);
}
if (n == 2)
{
return memoize_map.get(2);
}
HashSet<String> waysToClimb1Less = memoize_map.get(n-1);
if (waysToClimb1Less == null)
{
waysToClimb1Less = findWaysToClimbNStairs(n-1);
memoize_map.put(n-1, waysToClimb1Less);
} else {
System.out.println("1) ready reuse for " + (n-1));
}
HashSet<String> waysToClimb2Less = memoize_map.get(n-2);
if (waysToClimb2Less == null)
{
waysToClimb2Less = findWaysToClimbNStairs(n-2);
memoize_map.put(n-2, waysToClimb2Less);
} else {
System.out.println("2) ready reuse for " + (n-2));
}
for (String wayToClimb1Less : waysToClimb1Less)
strings.add("1" + wayToClimb1Less);
for (String wayToClimb2Less : waysToClimb2Less)
strings.add("2" + wayToClimb2Less);
return strings;
}
public static void test_stairs(int n, int expected_count)
{
System.out.println("test stairs for n = " + n);
HashSet<String> strings = findWaysToClimbNStairs(n );
System.out.println("num ways for climbing " + n + " = " + strings.size());
for (String s : strings)
{
System.out.println(s);
}
System.out.println("=== end of test stairs for n = " + n + " num ways = " + strings.size()
+ " expected num ways " + expected_count);
if (strings.size() == expected_count)
System.out.println("Matches expected count " + expected_count);
else
System.out.println("ERROR: Does not match expected count " + expected_count);
System.out.println("End of test... \n\n\n");
}
public static void main(String[] args) {
test_stairs(3, 3); //output == expected output = 3
test_stairs(4, 5); //output == expected output = 5
test_stairs(5, 8); //output == expected output = 8
}
}
You may be at at max possible valid wR, and then you just increment wR and read at it without checking for validity... so you may end up reading past the end of the array... Try it with array {1,1,1,100} and target sum 5.
- venera.varbanova April 05, 2015