Dynamic Programming : Medium

Jump Game

처음에는 다 더한 후 각자 위치에 올 수 있다는 거를 확인하고 그 값을 return 함 (저번에도 똑같이 풀었었음^^)

class Solution {
    public boolean canJump(int[] nums) {
        boolean answer = false;
        int total = 0; 
        
        for (int i = 0; i < nums.length; i++) {
            
            if (total < i) {
                return false; 
            }
            
            total += nums[i];
            
        }
        return true; 
        
    }
}

60/75 cases passed

그러다가 눈물을 머금고 원래 해야하는데로 DP로 풀었읍니다..

class Solution {
    public boolean canJump(int[] nums) {
        boolean answer = false;
        int total = 0; 
        
        
        boolean[] dp = new boolean[nums.length];
        dp[nums.length - 1] = true;
        
        if (nums.length <= 1) {
            return true;
        }
        
        for (int i = nums.length - 2; i >= 0; i--) {
            int high = Math.min(i + nums[i], nums.length - 1);
            
            for (int j = i + 1; j <= high; j++) {
                if (dp[j]) {
                    dp[i] = true;
                    break;
                }
            }
        }

        
        return dp[0]; 
        
    }
}

Runtime: 199 ms, faster than 33.76% of Java online submissions for Jump Game.
Memory Usage: 41 MB, less than 62.43% of Java online submissions for Jump Game.

호로로로로로롤
제 힘으로 풀어서 뿌듯하네요..ㅎ

enum Index {
    GOOD, BAD, UNKNOWN
}

public class Solution {
    public boolean canJump(int[] nums) {
        Index[] memo = new Index[nums.length];
        for (int i = 0; i < memo.length; i++) {
            memo[i] = Index.UNKNOWN;
        }
        memo[memo.length - 1] = Index.GOOD;

        for (int i = nums.length - 2; i >= 0; i--) {
            int furthestJump = Math.min(i + nums[i], nums.length - 1);
            for (int j = i + 1; j <= furthestJump; j++) {
                if (memo[j] == Index.GOOD) {
                    memo[i] = Index.GOOD;
                    break;
                }
            }
        }

        return memo[0] == Index.GOOD;
    }
}

이건 저번 루션이
제것이 더 낫다고 생각해요^^ (런타임은 모름;)

Unique Paths

class Solution {
    public int uniquePaths(int m, int n) {
        
        int[][] nums = new int[m][n];
        
        for (int i = 0; i < m; i++) {
            nums[i][0] = 1;
        }
        
        for (int j = 0; j < n; j++) {
            nums[0][j] = 1;
        }
        
        for (int k = 1; k < m; k++) {
            for (int l = 1; l < n; l++) {
                nums[k][l] = nums[k][l-1] + nums[k-1][l];
            }
        }
        
        
        return nums[m-1][n-1];
        
        
    }
}

Runtime: 0 ms, faster than 100.00% of Java online submissions for Unique Paths.
Memory Usage: 35.9 MB, less than 54.46% of Java online submissions for Unique Paths.

이거 기억나서 기억을 더듬어 풀었읍니다^^

class Solution {
    public int uniquePaths(int m, int n) {
        int[][] count = new int[m][n];
        
        for (int i = 0; i < m; i++) {
            count[i][0] = 1;
        }
        
        for (int j = 0; j < n; j++) {
            count[0][j] = 1;
        }
        
        for (int k = 1; k < m; k++) {
            for (int l = 1; l < n; l++) {
                count[k][l] = count[k - 1][l] + count[k][l - 1];
            }
        }
        
        return count[m-1][n-1];
    }
}

저번 루션이~ variable 쓴거 말고는 같네요

Coin Change

class Solution {
    public int coinChange(int[] coins, int amount) {
        int max = amount + 1;
        int[] dp = new int[max];
        Arrays.fill(dp, max);
        dp[0] = 0;
        
        for (int i = 1; i <= amount; i++) {
            for (int j = 0; j < coins.length; j++) {
                if (coins[j] <= i) {
                    dp[i] = Math.min(dp[i], dp[i-coins[j]] + 1);
                }
            }
        }
        
        return dp[amount] > amount ? -1 : dp[amount];
    }
}

Runtime: 11 ms, faster than 87.94% of Java online submissions for Coin Change.
Memory Usage: 38.7 MB, less than 40.19% of Java online submissions for Coin Change.

이거 저번에도 어려웠는데.. 이번에도 어렵고 시간이 없어서 저번 루션이 데려왔읍니다^^

Longest Strictly Increasing Subsequence

public class Solution {
    public int lengthOfLIS(int[] nums) {
        int[] dp = new int[nums.length];
        
        if (nums.length <= 1) return nums.length;
        
        int longest = 1;
        
        dp[0] = 1; 
        
        for (int i = 1; i < nums.length; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i]) {
                    dp[i] = Math.max(dp[j] + 1, dp[i]);
                }
                
            }
            longest = Math.max(dp[i], longest);
        }
        
        return longest;
    }
}

27/54 test cases passed

public class Solution {
    public int lengthOfLIS(int[] nums) {
        int[] dp = new int[nums.length];
        
        if (nums.length <= 1) return nums.length;
        
        int longest = 1;
        
        for (int k = 0; k < nums.length; k++) {
            dp[k] = 1;
        }
        
        for (int i = 1; i < nums.length; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i]) {
                    dp[i] = Math.max(dp[j] + 1, dp[i]);
                }
                
            }
            longest = Math.max(dp[i], longest);
        }
        
        return longest;
    }
}

Runtime: 61 ms, faster than 39.14% of Java online submissions for Longest Increasing Subsequence.
Memory Usage: 38.4 MB, less than 83.49% of Java online submissions for Longest Increasing Subsequence.

Initialize만 해주면 됨!!!!!!!!!!!!

public class Solution {
    public int lengthOfLIS(int[] nums) {
        int[] dp = new int[nums.length];
        int len = 0;
        for (int num : nums) {
            int i = Arrays.binarySearch(dp, 0, len, num);
            if (i < 0) {
                i = -(i + 1);
            }
            dp[i] = num;
            if (i == len) {
                len++;
            }
        }
        return len;
    }
}

저번 루션이
이거 이해 안되는 저...정상인가요^^

Runtime: 2 ms, faster than 99.07% of Java online submissions for Longest Increasing Subsequence.
Memory Usage: 38.9 MB, less than 32.62% of Java online submissions for Longest Increasing Subsequence.

저번 루션이가 훨씬 빠르네요..ㅎ
전씨와 함께 이해해 보고 싶네요