Dynamic Programming

1 44 Wildcard Match  双指针

    public boolean isMatch(String s, String p) {
        int idxs = 0, idxp = 0, idxstart = -1, idxmatch = 0;
        while (idxs < s.length())
        {
            if (idxp < p.length() && (s.charAt(idxs) == p.charAt(idxp) || p.charAt(idxp) == '?'))
            {
                idxp++; idxs++;
            }
            else if (idxp < p.length() && p.charAt(idxp) == '*')
            {
                idxstart = idxp;
                idxp++;
                idxmatch = idxs;
            }
            else if (idxstart != -1)
            {
                idxp = idxstart + 1;
                idxmatch++;
                idxs = idxmatch;
            }
            else
            {
                return false;
            }
        }
         while(idxp < p.length() && p.charAt(idxp) == '*'){
            idxp++;
        }
         return idxp == p.length();
    }

2 70 Climbing Stairs

    public int climbStairs(int n) {
        int i1 = 1;
        if (n == 1) return i1;
        int i2 = 2;
        for (int i = 3; i <= n; i++)
        {
            i2 = i1+i2;
            i1 = i2 - i1;
        }
        return i2;
    }

3 72 Edit Distance

    public int minDistance(String word1, String word2) {
        int[] dp = new int[word2.length() + 1];
        for (int i = 0; i < word2.length() + 1; i++)
        {
            dp[i] = i;
        }
        for (int i = 0; i < word1.length(); i++)
        {
            int[] cur = new int[word2.length() + 1];
            cur[0] = i + 1;
            for (int j = 0; j < word2.length(); j++)
            {
                if (word1.charAt(i) == word2.charAt(j)) cur[j + 1] = dp[j];
                else
                {
                    cur[j + 1] = Math.min(dp[j], Math.min(dp[j+1], cur[j])) + 1;
                }
            }
            dp = cur;
        }
        return dp[word2.length()];
    }

 5 月 8日 

4 96 Unique Binary Search Tree  卡特兰数

    public int numTrees(int n) {
        int[] res = new int[n + 1];
        res[0] = 1; res[1] = 1;
        for (int i = 2; i <= n; i++)
        {
            for (int j = 0; j < i; j++)
            {
                res[i] += res[j] * res[i - j - 1];
            }
        }
        return res[n];
    }

5 95 Unique Binary Search Tree  II   上一题变形

    public List<TreeNode> generateTrees(int n) {
        List<TreeNode> res = new ArrayList<>();
        if (n <= 0) return res;
        return help(1, n);
    }
    public List<TreeNode> help(int l, int r)
    {
        List<TreeNode> res = new ArrayList<>();
        if (l > r)
        {
            res.add(null);
            return res;
        }
        for (int i = l; i <= r; i++)
        {
            List<TreeNode> lres = help(l, i - 1);
            List<TreeNode> rres = help(i + 1, r);
            for (int j = 0; j < lres.size(); j++)
            {
                for (int k = 0; k < rres.size(); k++)
                {
                    TreeNode root = new TreeNode(i);
                    root.left = lres.get(j);
                    root.right = rres.get(k);
                    res.add(root);
                }
            }
        }
        return res;
    }

6 132 Palindrome Partitioning II    二位布尔和一维数

    public int minCut(String s) {
        char[] c = s.toCharArray();
        int n = c.length;
        int[] res = new int[n];
        boolean[][] help = new boolean[n][n];
        for (int i = 0; i < n; i++)
        {
            int min = i;
            for (int j = 0; j <= i; j++)
            {
                if (c[i] == c[j] && (j + 1 > i - 1 || help[j+1][i-1]))
                {
                    help[j][i] = true;
                    min = j == 0? 0 : Math.min(min, res[j - 1] + 1);
                }
            }
            res[i] = min;
        }
        return res[n - 1];
    }

7 139 word Break     分两段

    public boolean wordBreak(String s, List<String> d) {
        Set<String> dict = new HashSet<>(d);
        boolean [] breakable = new boolean[s.length()+1];
        breakable[0] = true;

        for (int i = 1; i <= s.length(); i++)
        {
            for (int j = 0; j < i; j++)
            {
                if (breakable[j] && dict.contains(s.substring(j,i)))
                {
                    breakable[i] = true;
                    break;
                }
            }
        }
        return breakable[s.length()];
    }

 5月9号

8  140 WORD BREAK ii深度优先搜索

    public List<String> wordBreak(String s, List<String> wordDict) {
            Set<String> words = new HashSet<>(wordDict);
            return DFS(s, words, new HashMap<String, LinkedList<String>>());
        }
        List<String> DFS(String s, Set<String> words, HashMap<String, LinkedList<String>> map){
            if (map.containsKey(s))  return map.get(s);
            LinkedList<String> res = new LinkedList<String>();
            if (s.length() == 0) { res.add(""); return res;}
            for (String word : words){
                if (s.startsWith(word)){
                    List<String> sublist = DFS(s.substring(word.length()), words, map);
                    for (String sub : sublist)
                        res.add(word + (sub.isEmpty() ? "":" ") + sub);
                }
            }
            map.put(s, res);
            return res;
        }

9 198 House Robber   分奇偶

private int rob(int[] num, int lo, int hi) {
    int include = 0, exclude = 0;
    for (int j = lo; j <= hi; j++) {
        int i = include, e = exclude;
        include = e + num[j];
        exclude = Math.max(e, i);
    }
    return Math.max(include, exclude);
}

10 213  House Robber  拍第一和最后 比较

    public int rob(int[] nums) {
        if (nums.length == 1) return nums[0];
    return Math.max(rob(nums, 0, nums.length - 2), rob(nums, 1, nums.length - 1));
    }
    private int rob(int[] num, int lo, int hi) {
    int include = 0, exclude = 0;
    for (int j = lo; j <= hi; j++) {
        int i = include, e = exclude;
        include = e + num[j];
        exclude = Math.max(e, i);
    }
    return Math.max(include, exclude);
}

11 221 Maximal Square  看上左

    public int maximalSquare(char[][] matrix) {
        if(matrix.length == 0) return 0;
        int m = matrix.length, n = matrix[0].length, res = 0;
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 1; i <= m; i++)
        {
            for (int j = 1; j <= n; j++)
            {
                if (matrix[i - 1][j - 1] == '1')
                {
                    dp[i][j] = Math.min(dp[i - 1][j], Math.min(dp[i - 1][j - 1], dp[i][j-1])) + 1;
                    res = Math.max(dp[i][j], res);
                }
            }
        }
        return res * res;
    }