back function (return number)
remember the structure
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;
}
}
Solution 2:
dp keywards: how many ways and optimal
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];
}
}
70. Climbing Stairs
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];
}
}