DP #494 Target Sum

class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        int n=nums.length;
        int ts = 0;
        for(int i:nums) ts+=i;
        if((ts-target)%2!=0)return 0;
        if((ts-target)<0)return 0;
        int tg = (ts-target)/2;
        // int[][] dp=new int[n][tg+1];
        // for(int[] i: dp)Arrays.fill(i,-1);
        // return func(n-1,nums,tg,dp);
        return tabOpt(nums,tg,n);
    }

    // Space optimised Tabulation solution
    int tabOpt(int[] nums, int t, int n){
        int[] dp = new int[t+1];
        dp[0]=(nums[0]==0)?2:1;
        for(int j=1;j<=t;j++){
            dp[j] = (j==nums[0])?1:0;
        }
        for(int i=1;i<n;i++){
            int[] cur=new int[t+1];
            for(int j=0;j<=t;j++){
                int tk = (j-nums[i]>=0) ? dp[j-nums[i]] : 0;
                int ntk = dp[j];
                cur[j] = tk+ntk;
            }
            dp=cur;
        }
        return dp[t];
    }

    // Tabulation solution
    int tab(int[] nums, int t, int n){
        int[][] dp = new int[n][t+1];
        dp[0][0]=(nums[0]==0)?2:1;
        for(int j=1;j<=t;j++){
            dp[0][j] = (j==nums[0])?1:0;
        }
        for(int i=1;i<n;i++){
            for(int j=0;j<=t;j++){
                int tk = (j-nums[i]>=0) ? dp[i-1][j-nums[i]] : 0;
                int ntk = dp[i-1][j];
                dp[i][j] = tk+ntk;
            }
        }
        return dp[n-1][t];
    }

    // Recursive solution
    int func(int i, int[] nums, int t,int[][]dp){
        if(t<0) return 0;
        if(i==0){
            if(t==0 && nums[i]==0) return dp[i][t]=2;
            if(t==0 || t==nums[i]) return dp[i][t]=1;
            return 0;
        } 
        if(dp[i][t] !=-1) return dp[i][t];
        int tk = func(i-1,nums,t-nums[i],dp);
        int ntk = func(i-1,nums,t,dp);
        return dp[i][t]=tk+ntk;
    }
}