题目明显可以转化为“是否存在和为sum/2的子数组” 所以就先求和，除以2，得出target sum 定义dp[i][s] 如果dp[i][s]=true, 表示nums[0, i]中存在一个subset的和为s 那么对于第i个数，能凑出s有两种情况： 1. 之前i-1个数已经能凑出s 2. 之前i-1的数能凑出s-num[i] 所以，dp[i][s] = dp[i-1][s] || dp[i-1][s-nums[i]]； 然后就正常2D->1D空间优化，只需要存dp[s] 空间：O(maxSum) 时间：O(maxSum * n) import java.util.*...

跟(一)同样的解法，dp定义也完全不用变。跑两遍而已 环形只影响最后一个房子的选择: - 如果偷了第0个房子，那最后一个房子就偷不了。 - 如果不偷第0个房子，那最后一个房子可以选择偷或着不偷 那岂不是把两个情况都跑一遍 挑个更好的就行了。。。 偷了第0个房子： 在第1个房子时， g(1)=nums[0] ～ 不偷1 f(1)=nums[0] ～ 偷1，理论上1不能偷，但是你就想象你也进了1，但是空手而归 因为偷了0，所以在最后一个房子n只能选g(n) 不偷第0个房子： 在第1个房子， g(1)=0 ～ 不偷1 f(1)=nums[1] ～ 偷1 因为没偷0，所...

import java.util.*; // F(i): max profit at nums[i], and rob nums[i] // = G(i-1) + nums[i] // G(i): max profit at nums[i], and do not rob nums[i] // = max(F(i-1), G(i-1)) // 空间优化：F/G of i only depends on F/G of i-1 // // 时间: O(n) 一个for loop // 空间: O(1) 只存上一轮的F和G public class Solution { publi...

时间: O(maxSum*N) 空间: O(maxSum) DP 定义: DP(i, j): # of ways num[0, i] can sum to j. DP(i, j) = DP(i-1, j + num[i]) + DP(i-1, j - num[i]) import java.util.*; public class Solution { public int findTargetSumWays (int[] nums, int target) { if (nums.length == 0) return 0; // 0<=s...

从下往上dp f(i,j) = Min{f(i+1,j), f(i+1,j+1)} + v(i,j) O(n^2), O(n^2) TODO: 第二个for-loop倒着走可以空间优化至O(n) import java.util.*; public class Solution { public int minTrace (int[][] triangle) { int len = triangle.length; if (len == 0) return 0; // f(i,j)=Min{f(i+1,j), f(i+1,j+1)} +...

就是三的解法loop个k遍。 profit[k,i]: k次买卖都在0～i天内执行，在第i天手上钱的最大值。 对于每个k，profit需要分两部计算 (i.e. buy and sell). 例子, k = 3 price: 3 16 6 14 10 19 pass1-buy: -3 -3 -3 -3 -3 -3 pass1-sell: 0 13 13 13 13 16 <- profit[1, i] pass2-buy: -3 -3 7 7 7 7 pass2-sell: 0 13 13 21 21 26 <- pr...

参考的leetcode#123。但是感觉leetcode的O(1)的解法思路有点反人类，就稍微转换了一下。 先看(四)的解法再看三(因为四不用空间优化, 好理解)。 举例 price: 3 16 6 14 10 19 大致可以理解为把#买卖股票的最好时机(一)#走三遍。 第一遍 和#买卖股票的最好时机(一)#一模一样，记录当前最低价minP。 C1就是1次买卖结束后你手上最多可能有的现金 C1[i] = max(P[j]-minP[j]), for all j<=i price: 3 16 6 14 10 19 minP: 3 3 3 3 3 3...

介绍两种时间O(n), 空间O(1)的解法 第一种(更符合DP思维): 定义F[i]: 在第i天持有股票的最大浮盈 情况1: 第i-1天已经持有股票，那么第i天继续持有的浮盈就是i-1天的浮盈加上i和i-1的价差： F[i-1]+(P[i]-P[i-1]) 情况2: 第i-1天未持有，第i天买入，此时浮盈为0 所以F[i] = max(情况1，情况2) = max(F[i-1]+(P[i]-P[i-1]), 0) 可见计算F[i]只需要昨天的state, 所以空间可以优化到O(1) import java.util.*; public class Solution { ...

首先比较容易会想到需要在dp时每一位考虑用了wildcard和没用wildcard的情况 没用wildcare的情况比较简单(见F(i)定义) 用了wildcare的情况为什么要考虑 G(i) 和 H(i)，请看以下案例： 10, 3, 10, 5, 6 G(2)的最优解是[1, 3, 10], i.e. 把第一个10换成1 H(2)的最优解时[3, 4], i.e. 把第二个10换成4 虽然此刻G(2)的长度大于H(2), 但是最终解选择的是H(2), i.e. [3, 4, 5, 6] 反之，如果案例变成 10，3，10，11，12 最终解在选择的是G(2), i.e. [1, 3,...

假dp 思路和连续子数组的最大和一模一样的 只需要多记录当前最优解的长度和endingIndex(为了在Sum相同的情况下比较长度，和之后还原SubArray). 这里把global和local的GSS的参数存成两个int[3]。具体逻辑看comment。 时间：O(n), 每个数visit一次 空间：O(1), 两个int[3]. import java.util.*; public class Solution { public int[] FindGreatestSumOfSubArray (int[] array) { if (array.length &lt...

就是(一)的衍生 需要多一个mem2记录每个数在以它结尾的LIS中的index。 看懂了(一)的O(nlogn)解这个基本也就懂了。 import java.util.*; public class Solution { public int[] LIS (int[] arr) { if (arr.length <= 1) return arr; // mem[i]: 长度为i+1的LIS的最后一个数的最优值(i.e. 最小). int[] mem = new int[arr.length]; // mem2[i]:...

就是(一)的O(nlogn)解 https://blog.nowcoder.net/n/dae14ef8bd484b01b541da73a155d9a2 import java.util.*; public class Solution { public int LIS (int[] a) { if (a.length <= 1) return a.length; int[] mem = new int[a.length]; mem[0] = a[0]; int lenLIS = 1; fo...

经典的LIS问题的最简形态(求LIS长度) 核心逻辑是: mem[n]: 长度为n+1的LIS的最后一个数的最优值(i.e. 最小). 有O(n^2)和O(nlogn)时间两种解。 import java.util.*; // time O(nlogn) solution // 视频讲解 https://www.youtube.com/watch?v=l2rCz7skAlk public class Solution { public int LIS (int[] arr) { if (arr.length <=1 ) return arr.length...

import java.util.*; // time O(n^2) solution. public class Solution { public int LIS (int[] arr) { if (arr.length <= 1) return arr.length; // F(i): length of LCI ending with arr[i]. int[] mem = new int[arr.length]; Arrays.fill(mem, 1); // F(i) = MAX...