什么时候用记忆搜索

初始状态不好弄 Iteration不好写

140. Word Break II

DFS that use a hashmap to keep the result. Pay attention to what should be included in the base case, should not be a complete empty string, since every other result need to be built upon the base case so we append " " to the base case.(We can think of it as a stack) And to keep track of what we have generated for now, keep a hashmap of index i and a list of strings which defines the situation when we break at index i to a list of strings.

This solution is not my own.. And I think we need to judge whether to return the result in the returned parameter or in the passed in parameter or not.

public class Solution {
    public List<String> wordBreak(String s, List<String> wordDict) {
        List<String> res = new ArrayList<String>();
        //Turn the representation to a HashSet
        HashSet<String> set = new HashSet();
        int maxLen = 0;
        for(String str : wordDict){
            set.add(str);
            maxLen = Math.max(maxLen,str.length());
        }
        return dfs(s,set,0,new HashMap<Integer,List<String>>(), maxLen);
    }

    public List<String> dfs(String s,HashSet<String> wordDict,int start,HashMap<Integer,List<String>> map,int maxLength){
        if(map.containsKey(start)) return map.get(start);
        List<String> rst = new ArrayList<String>();
        if(start >= s.length()) {
            rst.add(""); 
            return rst;
        }
        for(int i = start; i - start <= maxLength && i < s.length(); i++){
            String str = s.substring(start, i + 1);

            if(wordDict.contains(str)){
                List<String> afterWards = dfs(s, wordDict,i + 1,map, maxLength);
                for(String next : afterWards){
                    if(i + 1 < s.length()) rst.add(str + " " + next);
                    else rst.add(str);
                }
            }
        }

        map.put(start, rst);
        return rst;
    }
}

329. Longest Increasing Path in a Matrix

DFS from every point(see it as the start point) and keep the max result

public class Solution {
    //DFS
    public int longestIncreasingPath(int[][] matrix) {
        int result = 0;
        int m = matrix.length;
        if(matrix == null || m==0) return 0;
        int n = matrix[0].length;
        int[][] memo = new int[m][n];
        for(int i = 0;i < m;i++){
            for(int j = 0;j < n;j++){
                int cur = helper(matrix,i,j,memo,Integer.MIN_VALUE);
                result = Math.max(result,cur);
            }
        }
        return result;

    }
    /** memo stores the longest increasing path start from (i,j)
     Since we keep the computed value in memo array we do not need a visited array
    //pre参数的设置非常巧妙,如果不用这个参数，则我们需要在代码里进行四个方向的的比较*/
    public int helper(int[][] matrix,int i,int j,int[][] memo,int pre){
        int m = matrix.length;
        int n = matrix[0].length;
        //if the value have been computed before,simply return it
        if(i<0||j<0||i>=m||j>=n||matrix[i][j] <= pre){
            return 0;
        }
        if(memo[i][j]!=0){
            return memo[i][j];
        }
        //4 direction
        int cur = matrix[i][j];
        int tmp = 0;
        tmp = Math.max(helper(matrix,i-1,j,memo,cur),tmp);
        tmp = Math.max(helper(matrix,i+1,j,memo,cur),tmp);
        tmp = Math.max(helper(matrix,i,j-1,memo,cur),tmp);
        tmp = Math.max(helper(matrix,i,j+1,memo,cur),tmp);
        memo[i][j] = tmp + 1;
        return (tmp+1);
    }
}