leetcode解题: Graph Valid Tree (261)

发表于 2017-03-08 | 分类于刷题总结

Given n nodes labeled from 0 to n - 1 and a list of undirected edges (each edge is a pair of nodes), write a function to check whether these edges make up a valid tree.

For example:

Given n = 5 and edges = [[0, 1], [0, 2], [0, 3], [1, 4]], return true.

Given n = 5 and edges = [[0, 1], [1, 2], [2, 3], [1, 3], [1, 4]], return false.

Hint:

Given n = 5 and edges = [[0, 1], [1, 2], [3, 4]], what should your return? Is this case a valid tree?
According to the definition of tree on Wikipedia: “a tree is an undirected graph in which any two vertices are connected by exactly one path. In other words, any connected graph without simple cycles is a tree.”
Note: you can assume that no duplicate edges will appear in edges. Since all edges are undirected, [0, 1] is the same as [1, 0] and thus will not appear together in edges.

总结

此题用Union Find最简便，DFS 和 BFS 都可以。

解法1： DFS

按照题目意思，这是一个undirectedgraph判定是否是tree的问题，那么一个无向图要满足两个条件。一个是要全连通，另一个是要没有环。
基本思想是用DFS遍历，如果遍历到之前遇过的节点说明有环。遍历之后如果还有没有遍历过的节点那么就不是全通图。

Java

public class Solution {
    public boolean validTree(int n, int[][] edges) {
		// Construct the graph using hashmap
		// Empty Tree
		// Need to satisfy two conditions, 1) all nodes are linked 2) no cycle in the list
		if ((edges.length == 0 || edges[0].length == 0)) {
		    return n == 1 || n == 0;
		}
		HashMap<Integer, List<Integer>> map = new HashMap<Integer, List<Integer>>();
		for (int[] edge: edges) {
			if (!map.containsKey(edge[0])) {
				map.put(edge[0], new ArrayList<Integer>());
			}
			if (!map.containsKey(edge[1])) {
				map.put(edge[1], new ArrayList<Integer>());
			}
			map.get(edge[0]).add(edge[1]);
			map.get(edge[1]).add(edge[0]);
		}
	
		List<Boolean> visited = new ArrayList<Boolean>(n);
		for (int i = 0; i < n; ++i) {
		    visited.add(false);
		}
		boolean res = dfs(map, visited, 0, -1);
		if (!res) {
			return false;
		}
		for (boolean node: visited) {
			if (!node) {
				return false;
			}
		}
		return true;
    }
	private boolean dfs(HashMap<Integer, List<Integer>> map, List<Boolean> visited, int cur, int prev) {
		if (visited.get(cur)) {
			return false;
		}
		// prev records the node that link to the current dfs function call
		visited.set(cur, true);
		List<Integer> connected = map.get(cur);
		if (connected == null) {
		    return false;
		}
		for (int node: connected) {
		    if (node != prev) {
    			boolean res = dfs(map, visited, node, cur);
    			if (!res) {
    				return false;
    			}
		    }
		}
		return true;
	}
			
}

解法2： BFS

BFS 的思想和DFS的基本一致。要注意的是，在存储图的信息的时候，用一个Set比较方便。因为之后当我们在扫描一个节点连接的节点时，要删除对应节点中的edge（就是a连向b，那么b的相连node中一定有a，为了避免出现再遇到a，需要把对应的a从b相连的节点的list中删除，用set比较方便的解决此问题）
同时用一个set来维护已经访问过的节点。
Java

public class Solution {
	public boolean validTree(int n, int[][] edges) {
		if (edges.length == 0 || edges[0].length == 0) {
			return n == 1 || n == 0;
		}
		
		HashMap<Integer, Set<Integer>> map = new HashMap<Integer, Set<Integer>>();
		for (int[] edge: edges) {
			if (!map.containsKey(edge[0])) {
				map.put(edge[0], new HashSet<Integer>());
			}
			if (!map.containsKey(edge[1])) {
				map.put(edge[1], new HashSet<Integer>());
			}
			map.get(edge[0]).add(edge[1]);
			map.get(edge[1]).add(edge[0]);
		}
		
		// Start BFS
		Queue<Integer> queue = new LinkedList<Integer>();   
		Set<Integer> set = new HashSet<Integer>();
		queue.offer(0);
		set.add(0);
		while (!queue.isEmpty()) {
		    int node = queue.poll();
		    Set<Integer> elements = map.get(node);
		    if (elements != null) {
		        for (int element: elements) {
		            if (set.contains(element)) {
		                return false;
		            }
		            queue.offer(element);
		            set.add(element);
		            map.get(element).remove(node);
		        }
		    }
		    
		}
		
		// Check the length of Set
		return set.size() == n;
	
	}
}

解法3： Union Find

Union Find的算法就不详述了。Union Find很适合来解决Graph找circle的问题。这里的思路是如果两个node同属于一个parent那么就有circle存在。
如果不属于同一个parent，那么就把他们union起来成为一个group.
要注意的是最后如果没有出现circle，要比较一下是否每一个node都连接起来了，用edges.length == n - 1就可以判断
Java

public class Solution {
    public boolean validTree(int n, int[][] edges) {
        
        
        int[] parents = new int[n];
        Arrays.fill(parents, -1);
        for (int[] edge: edges) {
            int x = find(parents, edge[0]);
            int y = find(parents, edge[1]);
            if (x == y) {
                return false;
            }
            parents[x] = y;
        }
        
        return edges.length == n - 1;
        
    }
    
    int find(int[] parents, int x) {
        while (parents[x] != -1) x = parents[x];
        return x;
    }
}

leetcode solution: Reconstruct Itinerary (332)

发表于 2017-03-05 | 分类于刷题总结

Given a list of airline tickets represented by pairs of departure and arrival airports [from, to], reconstruct the itinerary in order. All of the tickets belong to a man who departs from JFK. Thus, the itinerary must begin with JFK.

Note:
If there are multiple valid itineraries, you should return the itinerary that has the smallest lexical order when read as a single string. For example, the itinerary [“JFK”, “LGA”] has a smaller lexical order than [“JFK”, “LGB”].
All airports are represented by three capital letters (IATA code).
You may assume all tickets form at least one valid itinerary.
Example 1:
tickets = [[“MUC”, “LHR”], [“JFK”, “MUC”], [“SFO”, “SJC”], [“LHR”, “SFO”]]
Return [“JFK”, “MUC”, “LHR”, “SFO”, “SJC”].
Example 2:
tickets = [[“JFK”,”SFO”],[“JFK”,”ATL”],[“SFO”,”ATL”],[“ATL”,”JFK”],[“ATL”,”SFO”]]
Return [“JFK”,”ATL”,”JFK”,”SFO”,”ATL”,”SFO”].
Another possible reconstruction is [“JFK”,”SFO”,”ATL”,”JFK”,”ATL”,”SFO”]. But it is larger in lexical order.

解法1：建图 + DFS

首先是建图的思想，这题看起来就要用DFS，可是没有图可以操作，对于这类的问题要想到用一个Hashmap来构造图的边的关系。
这里有一个小的trick是用到了PriorityQueue，因为最后的结果是要排序后较小的，那么我们构建hashmap的时候就要把每一个start对应的destination排好序，我们就可以用PQ来存储。
而题目有一个隐含的条件就是一定有解，那么如果我们在搜索碰到一个没有对应destination的城市的时候，他一定是要求的最后一个string。
所以我们在写DFS的时候，要把res.add(cur)放在while语句之后。

Java

public class Solution {
    public List<String> findItinerary(String[][] tickets) {
        
        // Construct the graph, using HashMap
        HashMap<String, PriorityQueue<String>> map = new HashMap<String, PriorityQueue<String>>();
        
        for (String[] pair: tickets) {
            if (map.containsKey(pair[0])) {
                map.get(pair[0]).add(pair[1]);
            } else {
                map.put(pair[0], new PriorityQueue<String>());
                map.get(pair[0]).add(pair[1]);
            }
        }
        
        // DFS the map and construct the itinerary
        List<String> res = new ArrayList<String>();
        dfs(map, "JFK", res);
        Collections.reverse(res);
        return res;
        
    }
    
    void dfs(HashMap<String, PriorityQueue<String>> map, String cur, List<String> res) {
        while (map.containsKey(cur) && !map.get(cur).isEmpty()) {
            dfs(map, map.get(cur).poll(), res);
        }
        res.add(cur);
        
    }
}

leetcode解题: Find Bottom Left Tree Value (513)

发表于 2017-03-05 | 分类于刷题总结

Given a binary tree, find the leftmost value in the last row of the tree.

Example 1:
Input:

1
2
3

  2
 / \
1   3

Output:
1
Example 2:
Input:

Output:
7
Note: You may assume the tree (i.e., the given root node) is not NULL.

解法1：DFS, O(N)

这题code写起来很简单，思路是这样的：每到一层第一个扫描到的可能就是我们要找的node。那么不断的更新这个node的值最后当遍历完这个树之后就可以得到答案了。
DFS遍历的时候维护一个全局变量maxdepth，然后每下一层就更新一下当前的depth，如果depth比maxdepth大，说明当前到达的是一个新层，而且访问的一定是这一层的最左的元素。
Java

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    int val = 0;
    int maxDepth = 0;
    public int findBottomLeftValue(TreeNode root) {
        
        dfs(root, 1);
        return val;
    }
    
    void dfs(TreeNode root, int depth) {
        if (root == null) {
            return;
        }
        
        if (depth > maxDepth) {
            maxDepth = depth;
            val = root.val;
        }
        
        if (root.left != null) {
            dfs(root.left, depth + 1);
        }
        
        if (root.right != null) {
            dfs(root.right, depth + 1);
        }
    }
    
    
    
}

leetcode solution: The Maze (490)

发表于 2017-03-05 | 分类于刷题总结

There is a ball in a maze with empty spaces and walls. The ball can go through empty spaces by rolling up, down, left or right, but it won’t stop rolling until hitting a wall. When the ball stops, it could choose the next direction.

Given the ball’s start position, the destination and the maze, determine whether the ball could stop at the destination.

The maze is represented by a binary 2D array. 1 means the wall and 0 means the empty space. You may assume that the borders of the maze are all walls. The start and destination coordinates are represented by row and column indexes.

Example 1

Input 1: a maze represented by a 2D array

Input 2: start coordinate (rowStart, colStart) = (0, 4)
Input 3: destination coordinate (rowDest, colDest) = (4, 4)
alt text
Output: true
Explanation: One possible way is : left -> down -> left -> down -> right -> down -> right.

Example 2

Input 1: a maze represented by a 2D array

Input 2: start coordinate (rowStart, colStart) = (0, 4)
Input 3: destination coordinate (rowDest, colDest) = (3, 2)
alt text
Output: false
Explanation: There is no way for the ball to stop at the destination.

Note:
There is only one ball and one destination in the maze.
Both the ball and the destination exist on an empty space, and they will not be at the same position initially.
The given maze does not contain border (like the red rectangle in the example pictures), but you could assume the border of the maze are all walls.
The maze contains at least 2 empty spaces, and both the width and height of the maze won’t exceed 100.

解法1：DFS + Memorization

这题和一般的地图题或者是有一题岛屿的题目类似，都可以用DFS来解决。这里的难点或者是区别在，球会一直往一个方向滚直到撞到了墙。所以在设计dfs程序的时候要考虑这个问题，可以用一个while循环解决。另外，对于已经访问过的点，不需要额外的申请一个空间来存储，只需要把已经访问过的node对应的maze的值设为-1就可。
对于dfs的优化呢，可以用一个dp矩阵来记录每一个扫描过的初始节点是否有解来剪掉一些枝

Java
public class Solution { public boolean hasPath(int[][] maze, int[] start, int[] destination) { if (maze.length == 0 || maze[0].length == 0) { return true; } int[][] dp = new int[maze.length][maze[0].length]; for (int[] row: dp) { Arrays.fill(row, -1); } return dfs(maze, start[0], start[1], destination, dp); } private boolean dfs(int[][] maze, int i, int j, int[] destination, int[][] dp) { if (i == destination[0] && j == destination[1]) { return true; } if (dp[i][j]!= -1) { return dp[i][j] == 1 ? true: false; } boolean res = false; int[][] directions = {{0,-1},{-1,0},{0,1},{1,0}}; maze[i][j] = -1; for (int[] dir: directions) { int x = i, y = j; int xinc = dir[0]; int yinc = dir[1]; while (x >= 0 && x < maze.length && y >= 0 && y < maze[0].length && maze[x][y] != 1) { x += xinc; y += yinc; } x -= xinc; y -= yinc; if (maze[x][y] != -1) { res = res || dfs(maze, x,y, destination, dp); } } dp[i][j] = res? 1: 0; maze[i][j] = 0; return res; } }

leetcode解题: Clone Graph (133)

发表于 2017-03-05 | 分类于刷题总结

Clone an undirected graph. Each node in the graph contains a label and a list of its neighbors.

OJ’s undirected graph serialization:
Nodes are labeled uniquely.

We use # as a separator for each node, and , as a separator for node label and each neighbor of the node.
As an example, consider the serialized graph {0,1,2#1,2#2,2}.

The graph has a total of three nodes, and therefore contains three parts as separated by #.

First node is labeled as 0. Connect node 0 to both nodes 1 and 2.
Second node is labeled as 1. Connect node 1 to node 2.
Third node is labeled as 2. Connect node 2 to node 2 (itself), thus forming a self-cycle.
Visually, the graph looks like the following:

   1
  / \
 /   \
0 --- 2
     / \
     \_/

解法1：HashMap + DFS, O(N) Time + O(N) Space

思路和有一题linkedlist有random pointer的一样，要分两步进行，一个是要遍历整个图（可选dfs或者bfs），另外要用一个hashmap来记录node和node之间的对应关系。

Java

/**
 * Definition for undirected graph.
 * class UndirectedGraphNode {
 *     int label;
 *     List<UndirectedGraphNode> neighbors;
 *     UndirectedGraphNode(int x) { label = x; neighbors = new ArrayList<UndirectedGraphNode>(); }
 * };
 */
public class Solution {
    public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
        if (node == null) {
            return node;
        }
        
        HashMap<UndirectedGraphNode, UndirectedGraphNode> map = new HashMap<UndirectedGraphNode, UndirectedGraphNode>();
        dfs(node, map);
        for (UndirectedGraphNode old: map.keySet()) {
            if (node.neighbors != null) {
                List<UndirectedGraphNode> ns = new ArrayList<UndirectedGraphNode>();
                for (int i = 0; i < old.neighbors.size(); ++i) {
                    ns.add(map.get(old.neighbors.get(i)));
                }
                map.get(old).neighbors = ns;
            }
        }
        
        return map.get(node);
    }
    
    void dfs(UndirectedGraphNode node, HashMap<UndirectedGraphNode, UndirectedGraphNode> map) {
        if (node == null) {
            return;
        }
        if (!map.containsKey(node)) {
            // Delay the assignment of neighbors
            UndirectedGraphNode cloned = new UndirectedGraphNode(node.label);
            map.put(node, cloned);
            if (node.neighbors!= null) {
                for (int i = 0; i < node.neighbors.size(); ++i) {
                    dfs(node.neighbors.get(i), map);
                }
            }
        }
    }
}

leetcode解题: Partition Equal Subset Sum (416)

发表于 2017-02-20 | 分类于刷题总结

Given a non-empty array containing only positive integers, find if the array can be partitioned into two subsets such that the sum of elements in both subsets is equal.

Note:
Each of the array element will not exceed 100.
The array size will not exceed 200.
Example 1:

Input: [1, 5, 11, 5]

Output: true

Explanation: The array can be partitioned as [1, 5, 5] and [11].
Example 2:

Input: [1, 2, 3, 5]

Output: false

Explanation: The array cannot be partitioned into equal sum subsets.

解法1：DP: O(N*M), M是要找的子数组的和的大小。

这题参考了这个的解法，这一类的dp的题目里，dp[i]的数组的下标往往表示的是能取得值。
这里呢，首先想到要能分成两个同等大小的数组，原数组的和一定必须是偶数，而且这样的话每一个子数组的和是sum/2
有了这个之后，dp[i]的定义就变成了原数组是否有一个子数组他的和是i。
进一步，我们可以遍历整个数组，对于每一个数x，我们从target开始往下update， dp[x] = dp[x] || dp[target - x]
就是说，如果dp[x]要存在的话，dp[target - x]一定也存在。

C++

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        if (nums.size() <= 1) {
            return false;
        }
        
        int sum = accumulate(nums.begin(), nums.end(), 0); 
        if (sum % 2 != 0) {
            return false;
        }
        
        int target = sum / 2;
        vector<bool> dp(target + 1, false);
        dp[0] = true;
        for (int i = 0; i < nums.size(); ++i) {
            for (int j = target; j >= nums[i]; --j) {
                dp[j] = dp[j] || dp[j - nums[i]];
            }
        }
        return dp[target];
    }
};

Java

Leetcode解题: Range Sum Query 2D - Immutable

发表于 2017-02-20 | 分类于刷题总结

Given a 2D matrix matrix, find the sum of the elements inside the rectangle defined by its upper left corner (row1, col1) and lower right corner (row2, col2).

alt text
The above rectangle (with the red border) is defined by (row1, col1) = (2, 1) and (row2, col2) = (4, 3), which contains sum = 8.

Example:
Given matrix = [
[3, 0, 1, 4, 2],
[5, 6, 3, 2, 1],
[1, 2, 0, 1, 5],
[4, 1, 0, 1, 7],
[1, 0, 3, 0, 5]
]

sumRegion(2, 1, 4, 3) -> 8
sumRegion(1, 1, 2, 2) -> 11
sumRegion(1, 2, 2, 4) -> 12
Note:
You may assume that the matrix does not change.
There are many calls to sumRegion function.
You may assume that row1 ≤ row2 and col1 ≤ col2.

解法1：DP: O(N^2) Initialization, O(1) Function Call

这题不难，题目意思是里面的程序会要call很多次。如果不做优化的话每次的成本都是O(N^2).
如果我们先预处理一下，把每一个点的累计和存储一下，就是说dp[i][j]是从[0][0]到[i][j]的和。
那么当要计算子矩阵的和的时候，我们可以得到如下的关系

1	sum[i][j] = dp[i][j] - dp[i][j-1] - dp[i-1][j] + dp[i-1][j-1]

C++

class NumMatrix {
public:
    NumMatrix(vector<vector<int>> matrix) {
        // initialize dp
        dp = matrix;    // copy assignment operator
        for (int i = 0; i < matrix.size(); ++i) {
            for (int j = 0; j < matrix[i].size(); ++j) {
                dp[i][j] = (i == 0?0: dp[i - 1][j]) + (j == 0?0:dp[i][j - 1]) 
                - (i > 0 && j > 0?dp[i -1][j - 1]: 0) + matrix[i][j];
            }
        }
    }
    
    int sumRegion(int row1, int col1, int row2, int col2) {
        return dp[row2][col2] - (row1 > 0? dp[row1 - 1][col2]: 0) - (col1 > 0 ? dp[row2][col1 - 1]: 0) + (row1 > 0 && col1 >0 ? dp[row1 - 1][col1 - 1]: 0);
    }
    
private:
    vector<vector<int>> dp;
};
/**
 * Your NumMatrix object will be instantiated and called as such:
 * NumMatrix obj = new NumMatrix(matrix);
 * int param_1 = obj.sumRegion(row1,col1,row2,col2);
 */

Java

Leetcode解题: Best time to buy and sell stock with cooldown (309)

发表于 2017-02-19 | 分类于刷题总结

Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times) with the following restrictions:

You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).
After you sell your stock, you cannot buy stock on next day. (ie, cooldown 1 day)
Example:

prices = [1, 2, 3, 0, 2]
maxProfit = 3
transactions = [buy, sell, cooldown, buy, sell]

解法1：DP O(N) Time + O(N) Space

这题主要要想到用两个数组来记录每一天的两种状态。一个是第i天持有股票，一个是第i天未持有股票。
用sell和buy代表两个数组。buy就是第i天持有股票的投资组合的最大市值。sell就是第i天未持有股票时的投资组合的最大市值。
那么初始状态sell[0] = 0, buy[0] = -prices[0]这是表示如果第一天持有股票的话一定是买入操作，那么需要花去prices[0]的钱。
那么每一天投资组合的演化可以得出下面的关系

第i天未持股的最大市值要么是上一天1）持股2）未持股。
如果未持股则市值不变，如果持股那么因为第i天一定要卖掉，
所以如果上一天持股的话则今天的最大市值只能是buy[i-1]+Prices[i]
sell[i] = max(sell[i - 1], buy[i - 1] + prices[i])
同理，
buy[i] = max(buy[i - 1], sell[i - 2] - prices[i])

依此写出如下程序，如果要求的话可以对空间进一步优化成O(1)
C++

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        if (prices.size() <= 1) {
            return 0;
        }
        int n = prices.size();
        vector<int> sell(n, 0);
        vector<int> buy(n, 0);
        buy[0] = -prices[0];
        for (int i = 1; i < n; ++i) {
            sell[i] = max(sell[i - 1], buy[i - 1] + prices[i]);
            buy[i] = max(buy[i - 1], (i > 1? sell[i - 2]:0) - prices[i]);
        }
        return sell[n - 1];
    }
};

解法1：另外一种解释

以下的说明直接来自leetcode discussion

1. Define States
To represent the decision at index i:
buy[i]: Max profit till index i. The series of transaction is ending with a buy.
sell[i]: Max profit till index i. The series of transaction is ending with a sell.
To clarify:
Till index i, the buy / sell action must happen and must be the last action. It may not happen at index i. It may happen at i - 1, i - 2, ... 0.
In the end n - 1, return sell[n - 1]. Apparently we cannot finally end up with a buy. In that case, we would rather take a rest at n - 1.
For special case no transaction at all, classify it as sell[i], so that in the end, we can still return sell[n - 1]. Thanks @alex153 @kennethliaoke @anshu2.
2. Define Recursion
buy[i]: To make a decision whether to buy at i, we either take a rest, by just using the old decision at i - 1, or sell at/before i - 2, then buy at i, We cannot sell at i - 1, then buy at i, because of cooldown.
sell[i]: To make a decision whether to sell at i, we either take a rest, by just using the old decision at i - 1, or buy at/before i - 1, then sell at i.
So we get the following formula:
buy[i] = Math.max(buy[i - 1], sell[i - 2] - prices[i]);   
sell[i] = Math.max(sell[i - 1], buy[i - 1] + prices[i]);
3. Optimize to O(1) Space
DP solution only depending on i - 1 and i - 2 can be optimized using O(1) space.
Let b2, b1, b0 represent buy[i - 2], buy[i - 1], buy[i]
Let s2, s1, s0 represent sell[i - 2], sell[i - 1], sell[i]
Then arrays turn into Fibonacci like recursion:
b0 = Math.max(b1, s2 - prices[i]);
s0 = Math.max(s1, b1 + prices[i]);
4. Write Code in 5 Minutes
First we define the initial states at i = 0:
We can buy. The max profit at i = 0 ending with a buy is -prices[0].
We cannot sell. The max profit at i = 0 ending with a sell is 0.

public int maxProfit(int[] prices) {
    if(prices == null || prices.length <= 1) return 0;
    int b0 = -prices[0], b1 = b0;
    int s0 = 0, s1 = 0, s2 = 0;
    for(int i = 1; i < prices.length; i++) {
    	b0 = Math.max(b1, s2 - prices[i]);
    	s0 = Math.max(s1, b1 + prices[i]);
    	b1 = b0; s2 = s1; s1 = s0;
    }
    return s0;
}

leetcode解题: Longest Palindromic Subsequence (516)

发表于 2017-02-16 | 分类于刷题总结

Given a string s, find the longest palindromic subsequence’s length in s. You may assume that the maximum length of s is 1000.

Example 1:
Input:

"bbbab" Output:4
One possible longest palindromic subsequence is “bbbb”.
Example 2:
Input:

"cbbd" Output:2
One possible longest palindromic subsequence is “bb”

解法1：DP: O(N^2)

字符串的问题的DP有的时候需要考虑2D的DP解法。这题就是一个列子。
假设dp[i][j]是指(i,j)的子字符串的LPS, 那么如果首尾字符相同的话
dp[i][j] = dp[i + 1][j - 1] + 2
如果不相同的话，可以是错位match，也就是说要么用上尾字符，要么用上头字符。
dp[i][j] = max(dp[i+1][j], dp[i][j-1])

C++

class Solution {
public:
    int longestPalindromeSubseq(string s) {
        
        if (s.size() == 0) return 0;
        
        int n = s.size() - 1;
        
        int dp[n + 1][n + 1] {0};
        
        for (int i = 0; i <= n; ++i) {
            dp[i][i] = 1;
        }
        
        for (int i = n - 1; i >= 0; --i) {
            for (int j = i + 1; j <= n; ++j) {
                if (s[i] == s[j]) {
                    dp[i][j] = dp[i + 1][j - 1] + 2;
                } else {
                    dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);
                }
            }
        }
        
        return dp[0][n];
    }
};

Java

leetcode解题: Coin Change (322)

发表于 2017-02-16 | 分类于刷题总结

You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

Example 1:
coins = [1, 2, 5], amount = 11
return 3 (11 = 5 + 5 + 1)

Example 2:
coins = [2], amount = 3
return -1.

Note:
You may assume that you have an infinite number of each kind of coin.

解法1：DP, O(N*M), N 是coin的个数，M是amount的数字

用DP来解，因为涉及到了“检验某一种步骤是否可行”。基本思路是假设dp[i]代表的是$i所需要的最少的coins的数目。
因为我们的coins的面额是已知的。那么对每一个coins的面额j
我们可以有如下的关系

1	dp[i + coins[j]] = min(dp[i] + 1, dp[i + coins[j]])

因为dp[i]已知，那么最多的coins就能确定是dp[i] + 1, 直接用下一个可用的coin即可。
然后对于coins的array和从1到i循环，不停的更新dp[i], dp[amount]就是我们要求的数值。
要注意的是，在更新一个dp[i‘]的时候，要保证dp[i]已知（！=INT_MAX)而且下标不要超界，还有coins[j]也不要超过INT_MAX (不会overflow)
可以用coins[j] <= INT_MAX - i
C++

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        vector<int> dp(amount + 1, INT_MAX);
        dp[0] = 0;  // initialize the first data point
        for (int i = 0; i <= amount; ++i) {
            for (int j = 0; j < coins.size(); ++j) {
                if (coins[j] != INT_MAX && i + coins[j] <= amount && dp[i] != INT_MAX) {
                    dp[i + coins[j]] = min(dp[i] + 1, dp[i + coins[j]]);
                }
            }
        }
        return dp[amount] == INT_MAX ? -1: dp[amount];
    }
};

Java

总结

解法1： DFS

解法2： BFS

解法3： Union Find

解法1：建图 + DFS

解法1：DFS, O(N)

解法1：DFS + Memorization

解法1：HashMap + DFS, O(N) Time + O(N) Space

解法1：DP: O(N*M), M是要找的子数组的和的大小。

解法1：DP: O(N^2) Initialization, O(1) Function Call

解法1：DP O(N) Time + O(N) Space

解法1： 另外一种解释

解法1：DP: O(N^2)

解法1：DP, O(N*M), N 是coin的个数，M是amount的数字

解法1：另外一种解释