class Solution {

    int res = 0;

    //List<List<Integer>> resList = new ArrayList<List<Integer>>();

    public int combinationSum4(int[] nums, int target) {

        Arrays.sort(nums);

        return back(target, 0,nums,new HashMap<Integer,Integer>());

    }

    int back(int target, int sum, int[] nums, Map<Integer,Integer> map){

        if(sum == target){

            return 1;

        }else if(sum > target) return 0;

        if(map.containsKey(sum)) return map.get(sum);

        int count = 0;

        for(int i = 0; i<nums.length; i++){

            count+= back(target, sum+nums[i],nums,map);

        }

        map.put(sum,count);

        return count;

    }

}

class Solution {

    public int combinationSum4(int[] nums, int target) {

        int[] dp = new int[target+1]; // how many cases for each number

        Arrays.sort(nums);

        for(int num:nums){

            if(num>target) continue;

            dp[num] = 1;

        }

        for(int i = 1;i <=target; i++){

            for(int num : nums){

                if(i<num) continue;

                dp[i] += dp[i-num];

            }

        }

        return dp[target];

    }

}

class Solution {

    //dp[n] = dp[n-1] + dp[n-2]

    //dp[1] : 1, dp[0] = 1 ,dp[2] = 2, dp[3] = 3

    public int climbStairs(int n) {

        int[] dp = new int[n+1];

        dp[0] = 1; dp[1] = 1;

        for(int i = 2; i<=n; i++){

            dp[i] = dp[i-1]+dp[i-2];

        }

        return dp[n];

    }

}