8052019

class  {
    public int removeDuplicates(int[] nums) {
        if(nums.length == 0){
            return 0;
        }
        int end = 0;
        for(int num:nums){
            if(num != nums[end]){
                end++;
                nums[end] = num;
            }
        }
        
        return end+1;
    }
}

class  {
    public int removeDuplicates(int[] nums) {
        if(nums.length <= 2){
            return nums.length;
        }
        int end = 1;
        for(int i=2; i<nums.length; i++){
            int num = nums[i];
            if(num != nums[end-1]){
                end++;
                nums[end] = num;
            }
        }
        
        return end+1;
    }
}

class  {
    public int rob(int[] nums) {
        if(nums.length == 0){
            return 0;
        }
        
        int pre2 = 0;
        int pre1 = 0;
        
        for(int num:nums){
            int cur = Math.max(pre2+num, pre1);
            pre2 = pre1;
            pre1 = cur;
        }
        
        return pre1;
    }
}

class  {
    public int numWays(int n, int k) {
        int result = 0;
        if(n<=0){
            return result;
        }
        int pre_same = k;
        int pre_diff = k*(k-1);
        if(n == 1){
            return k;
        }else if(n == 2){
            return k*k;
        }
        
        while(n>2){
            int cur_diff = pre_same*(k-1) + pre_diff*(k-1);
            int cur_same = pre_diff;
            pre_same = cur_same;
            pre_diff = cur_diff;
            n--;
        }
        
        return pre_same + pre_diff;
        
    }
}

class  {
    public int minCut(String s) {
        int[] result = new int[s.length()];
        
        for(int i=1; i<s.length(); i++){
            
            if(isPal(s, 0, i)){
                continue;
            }
            result[i] = Integer.MAX_VALUE;
            for(int j=0; j<i; j++){                
                if(isPal(s, j+1, i)){
                    result[i] = Math.min(result[j] + 1, result[i]);
                }
            }
        }
        
        return result[s.length()-1];
    }
    
    private boolean isPal(String s, int start, int end){
        while(start <= end){
            if(s.charAt(start) != s.charAt(end)){
                return false;
            }
            start++;
            end--;
        }
        
        return true;
    }
}

class Solution {
    public int minCut(String s) {
        int[] result = new int[s.length()];
        if(s.length() <= 1){
            return 0;
        }
        result[0] = 0;
        for(int i=1; i<s.length(); i++){
            int cur_result = Integer.MAX_VALUE;
            for(int j=0; j<i; j++){
                if(ifPalindrome(s.substring(j, i+1))){
                    if(j>0){
                       cur_result = Math.min(result[j-1]+1, cur_result); 
                    }else{
                        cur_result = Math.min(0, cur_result); 
                    }
                    
                }             
            }
            result[i] = Math.min(result[i-1]+1, cur_result);
        }
        
        return result[s.length()-1];
    }
    
         
    public boolean ifPalindrome(String subS){
        int start = 0;
        int end = subS.length()-1;

        while(start < end){
            if(subS.charAt(start) != subS.charAt(end)){
                return false;
            }
            start++;
            end--;
        }

        return true;
    }
    
}