Leetcode-DP
70
class Solution {
public int climbStairs(int n) {
if (n<1){
return 0;
}
else if(n==1)
return 1;
else if(n==2)
return 2;
else{
int ans = 0;
int a = 1, b=2;
for (int i=3; i<=n; i++){
ans = a + b;
a = b;
b = ans;
}
return ans;
}
}
}
91
https://www.tianmaying.com/tutorial/LC91
class Solution {
public int numDecodings(String s) {
if (s.length()==0)
return 0;
int[] dp = new int[s.length()+1];
dp[0] = 1;
for (int i=1; i<=s.length(); i++){
if (s.charAt(i-1) >'0' ){
dp[i] += dp[i-1];
}
if(i>1 && (s.substring(i-2, i).compareTo("09")>0) && ("27".compareTo(s.substring(i-2, i))>0)){
dp[i] += dp[i-2];
}
}
return dp[s.length()];
}
}
95
很奇怪，n=0处理
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<TreeNode> generate(int start, int end){
List<TreeNode> treeList = new ArrayList<TreeNode>();
if(start>end){
treeList.add(null);
return treeList;
}
for (int i=start; i<=end; i++){
List<TreeNode> leftList = generate(start, i-1);
List<TreeNode> rightList = generate(i+1, end);
for (int j=0; j<leftList.size(); j++){
for (int k=0; k<rightList.size(); k++){
TreeNode root = new TreeNode(i);
root.left = leftList.get(j);
root.right = rightList.get(k);
treeList.add(root);
}
}
}
return treeList;
}
public List<TreeNode> generateTrees(int n) {
if (n==0)
return new ArrayList<TreeNode>();
return generate(1, n);
}
}
96
1-dp
左右子树递归调用原来的dp值。
f(0) = 1
f(n) = f(0)*f(n-1) + f(1)f(n-2) + ... + f(n-2)f(1) + f(n-1)*f(0)
class Solution {
public int numTrees(int n) {
if(n==0)
return 0;
if(n==1)
return 1;
int[] dp = new int[n+1];
dp[0]=1;
dp[1]=1;
for (int i=2; i<=n; i++){
for (int j=0; j<i; j++){
dp[i] += dp[j]*dp[i-1-j];
}
}
return dp[n];
}
}
139
http://www.jianshu.com/p/bb07e7825212
import javax.swing.tree.TreeNode;
import java.util.List;
class Solution {
public boolean isContain(List<String> wordDict, String s){
for (String word : wordDict){
if(word.equals(s))
return true;
}
return false;
}
public boolean wordBreak(String s, List<String> wordDict) {
int length = s.length();
if (length==0)
return false;
boolean[] dp = new boolean[length+1];
dp[0] = true;
for (int i=1; i<=length; i++){
for (int j=i-1; j>=0; j--){
if (dp[j] && isContain(wordDict, s.substring(j, i))){
dp[i]=true;
break;
}
}
}
return dp[length];
}
}
198
class Solution {
public int rob(int[] nums) {
int a=0, b=0, c=0; //dpi, dpi-1, dpi-2
if(nums.length<1)
return 0;
else if(nums.length==1)
return nums[1];
else if(nums.length==2){
int ans = nums[1]>nums[0]? nums[1]: nums[0];
return ans;
}
c = nums[0];
b = nums[1]>nums[0] ? nums[1]: nums[0];
a = (nums[1]>nums[0]+nums[2])?nums[1]:nums[0]+nums[2];
for(int i=2;i<nums.length; i++){
int val1 = c+nums[i];
int val2 = b;
if (val1>val2){
a= val1;
}
else
a= val2;
c = b;
b = a;
}
return a;
}
}
213
参考198
是House Robber的扩展题（http://fisherlei.blogspot.com/2017/07/leetcode-house-robber-solution.html ），唯一的区别就是house 0 和house n-1相邻了。根据题目要求，不能抢劫相邻的房子，所以这个环把它拆开就两种可能：
- 抢劫house 0，那么就不能抢劫house n-1，所以抢劫的范围就是[0, n-2]
- 不抢劫house 0，那么就得从house 1开始抢，抢劫的范围就是[1, n-1]
对于#1和#2两种情况，都可以复用House Robber的代码， 最后比较一下这两种可能中，那个收入多即可。
class Solution {
public int maxVal(int a, int b){
return a>b?a:b;
}
public int rob(int[] nums) {
int size = nums.length;
if (size<1)
return 0;
if (size==1)
return nums[0];
else if (size==2)
return maxVal(nums[0],nums[1]);
int a=nums[0], b=maxVal(nums[0],nums[1]);
int res1 = maxVal(a,b);
for(int i=2; i<size-1; i++){
res1 = maxVal(a+nums[i], b);
a = b;
b = res1;
}
a = nums[1];
b=maxVal(nums[1], nums[2]);
int res2 = maxVal(a, b);
for(int i=3; i<size; i++){
res2 = maxVal(a+nums[i], b);
a = b;
b = res2;
}
return maxVal(res1, res2);
}
}
221
根据经验，一眼便看出这是一道 动态规划 题。我们用 dp[i][j] 表示以 matrix[i][j] 为右下角的最大全 1 正方形的边长，仔细思考，如何推得 dp[i][j] 的递推公式？
dp[i][j] 可以从三部分推得，首先是 dp[i-1][j-1]，然后是 matrix[i][j] 左边的连续 1 的个数，然后是 matrix[i][j] 上面连续 1 的个数，这三部分取最小值。于是我们可以维护三个数组，dp[i][j] 表示以 matrix[i][j] 为右下角的全 1 正方形的边长，a[i][j] 表示从 matrix[i][j] 往左的连续 1 的个数，b[i][j] 表示从 matrix[i][j] 往上的连续 1 的个数。
class Solution {
public int min3(int a, int b, int c){
if(a>b)
a=b;
if(a>c)
a=c;
return a;
}
public int maximalSquare(char[][] matrix) {
if(matrix.length==0 || matrix[0].length==0)
return 0;
int m = matrix.length;
int n = matrix[0].length;
int maxLength = 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] = min3(dp[i-1][j-1], dp[i-1][j], dp[i][j-1])+1;
maxLength = dp[i][j] > maxLength? dp[i][j] : maxLength;
}
}
return maxLength*maxLength;
}
}
264
Dp
https://discuss.leetcode.com/topic/21882/my-16ms-c-dp-solution-with-short-explanation
class Solution {
public int nthUglyNumber(int n) {
int[] dp = new int[n+1];
dp[0] = 1;
int i1=0;
int i2=0;
int i3=0;
for(int i=1; i<n; i++){
dp[i] = Math.min(Math.min(dp[i1]*2, dp[i2]*3), dp[i3]*5);
if(dp[i]==dp[i1]*2)
i1++;
if(dp[i]==dp[i2]*3)
i2++;
if(dp[i]==dp[i3]*5)
i3++;
}
return dp[n-1];
}
}
303
1-DP
边界条件可以写的更精致一些
class NumArray {
int[] sumI;
int[] nums;
public NumArray(int[] nums) {
this.nums = nums;
sumI = new int[nums.length];
int sum = 0;
for(int i=0; i<nums.length; i++){
sum += nums[i];
sumI[i] = sum;
}
}
public int sumRange(int i, int j) {
return sumI[j] - sumI[i] + nums[i];
}
}
/**
* Your NumArray object will be instantiated and called as such:
* NumArray obj = new NumArray(nums);
* int param_1 = obj.sumRange(i,j);
*/
416
1-dp-01pack
Ref-494
https://discuss.leetcode.com/topic/67539/0-1-knapsack-detailed-explanation/2
class Solution {
public boolean canPartition(int[] nums) {
int sum = 0;
for (int n : nums){
sum+=n;
}
if (sum%2==1)
return false;
System.out.println(sum);
sum /= 2;
boolean[] dp = new boolean[sum+1];
dp[0] = true;
for (int n : nums){
for (int v=sum; v>=n; v--){
dp[v] = dp[v] || dp[v-n];
}
}
if (dp[sum])
return true;
else
return false;
}
}
494
class Solution {
int cnt = 0;
public int findTargetSumWays(int[] nums, int S) {
if (nums.length<1)
return 0;
helper(nums, S, 0);
return cnt;
}
public void helper(int[] nums, int currentS, int index){
if (index >= nums.length){
if (currentS==0)
cnt++;
return;
}
helper(nums, currentS+nums[index], index+1);
helper(nums, currentS-nums[index], index+1);
}
}
2-增加记录
class Solution {
public int findTargetSumWays(int[] nums, int S) {
if (nums.length<1)
return 0;
Map<String, Integer> cntMap = new HashMap<>();
return helper(nums, S, 0, cntMap);
}
public int helper(int[] nums, int currentS, int index, Map<String, Integer> cntMap){
String key = index+"-"+currentS;
if (cntMap.containsKey(key))
return cntMap.get(key);
if (index == nums.length){
if (currentS==0)
return 1;
return 0;
}
int cntPlus = helper(nums, currentS+nums[index], index+1, cntMap);
int cnrMinus = helper(nums, currentS-nums[index], index+1, cntMap);
cntMap.put(key, cnrMinus+cntPlus);
return cnrMinus+cntPlus;
}
}
3-
0-1背包问题
class Solution {
public int findTargetSumWays(int[] nums, int S) {
int sum = 0;
for (int num : nums){
sum += num;
}
if (sum<S || (sum+S)%2==1)
return 0;
int newSum = (sum+S)/2;
int[] dp = new int[newSum+1];
dp[0] = 1;
for (int n : nums){
for(int v=newSum; v>=n; v--){
dp[v] += dp[v-n];
}
}
return dp[newSum];
}
}
650
1-Iteration
https://discuss.leetcode.com/topic/97752/very-simple-java-solution-with-detail-explanation/2
class Solution {
public int minSteps(int n) {
int ans = 0;
for(int i=2; i<=n; i++){
while (n%i==0){
ans += i;
n /= i;
}
}
return ans;
}
}
2-Dp
思路形同
class Solution {
public int minSteps(int n) {
int[] dp = new int[n+1];
for (int i=2; i<=n; i++){
dp[i] = i;
for (int j=i-1; j>1; j--){
if(i%j==0){
dp[i] = Math.min(dp[i], dp[j]+i/j);
}
}
}
return dp[n];
}
}