[dfs, dp] 494. Target Sum

You are given a list of non-negative integers, a1, a2, …, an, and a target, S. Now you have 2 symbols + and -. For each integer, you should choose one from + and – as its new symbol.

Find out how many ways to assign symbols to make sum of integers equal to target S.

Example 1:
Input: nums is [1, 1, 1, 1, 1], S is 3.
Output: 5
Explanation:

-1+1+1+1+1 = 3
+1-1+1+1+1 = 3
+1+1-1+1+1 = 3
+1+1+1-1+1 = 3
+1+1+1+1-1 = 3

There are 5 ways to assign symbols to make the sum of nums be target 3.
Note:
The length of the given array is positive and will not exceed 20.
The sum of elements in the given array will not exceed 1000.
Your output answer is guaranteed to be fitted in a 32-bit integer.

DFS的思路首先想出来,顺利写出来:

    public int findTargetSumWays(int[] nums, int S) {
        return helper(nums, S, 0, 0, 0);
    }
    
    private int helper (int[] nums, int S, int index, int sum, int count) {
        if (index == nums.length) {
            if (sum == S) return count + 1;
            else return count;
        } 
        int count1 = helper(nums, S, index + 1, sum + nums[index], count);
        int count2 = helper(nums, S, index + 1, sum - nums[index], count);
        return count1 + count2;
    }

这种recusion其实都类似,一般都在helper函数里需要给index,记录当前看到哪个元素;原函数需要什么就return什么(需要count就return count,需要所有的排列组合就return list或者set之类的)。

但是,recusion很慢,写的时候也能感觉到,各种排列组合应该有很多重复的时候。

一般,dfs的问题想improve,可以考虑dp。只是这个问题直接从dfs的code改成dp,无从下手。

要及时抛弃已经有的dfs code,重新想思路。

新思路:题目转化找到一个subset都是positive,剩下的subset都是negative,使得 P – N == target. 已知 P + N == sum, 则 2P = target + sum, p = (target + sum) / 2。题目转化成找到一个subset,使其和等于(target + sum) / 2。这个新问题,用dp做。

    private int helper(int[] nums, int target) {
        int[] dp = new int[target + 1]; //存有几种组合可以达到当前目标(1...target)
        dp[0] = 1;
        for (int n : nums) {
            for (int i = target; i >= n; i--) { //倒着看
                dp[i] += dp[i - n]; //新来的数是n,现在只要可以达到i-n就可以达到i
            }
        }
        return dp[target];
    }

可以考虑dp解决这个新问题也是一个模版,而且是典型的dp模版。

[LC 321]. Create Maximum Number

Given two arrays of length m and n with digits 0-9 representing two numbers. Create the maximum number of length k <= m + n from digits of the two. The relative order of the digits from the same array must be preserved. Return an array of the k digits. You should try to optimize your time and space complexity.

以下是在discussion中最好理解的也最clean的一种做法:

总体思路:每个array先组成最大的数字,然后在merge。第一个array先组成i位的数字,第二个再组成k-i位的,当试过所有的组合之后,就可以找到最大值。

细节实现:
1.对单个array找最大值,用stack。例如[9,1,5,8,3], 找到3位的最大值:准备一个stack,push 9,push 1,5比stack最上面的1大,而且array还剩3个元素,所以pop 1,push 5,8比5大,array还剩2个元素,所以pop 5,push 8,最后push 3.

2.merge的时候用两个pointer,指到两个array分别找到的最大值,谁指的数字比较大,当前的结果就取大的。当两个pointer指到的数字相等时,值得注意,需要看后面的数字谁比较大才能决定结果的当前位应该取哪个数字。例如combine [1,9]和[1,8,4],i和j分别指向第一个6和第二个6,结果先取哪个6需要看后面的数字哪个大。因为9比8大,最后得到19184。如果在第一步中随便取一个6,取到了第二个,就变成了18419.

    public int[] maxNumber(int[] nums1, int[] nums2, int k) {
        int len1 = nums1.length;
        int len2 = nums2.length;
        int[] res = new int[k];
        for (int i = Math.max(0, k - len2); i <= Math.min(k, len1); i++) {
            int[] n1 = maxArray(nums1, i);
            int[] n2 = maxArray(nums2, k - i);
            int[] n = merge(n1, n2, k);
            if (greater(n, 0, res, 0)) res = n;
        }

        return res;
    }

    private int[] merge(int[] a, int[] b, int k) {
        int[] ans = new int[k];
        for (int i = 0, j = 0, r = 0; r < k; r++) {
            ans[r] = greater(a, i, b, j) ? a[i++] : b[j++];
        }
        return ans;
    }

    private boolean greater(int[] a, int i, int[] b, int j) {
        while (i < a.length && j < b.length && a[i] == b[j]) {
            i++;
            j++;
        }
        return j == b.length || (i < a.length && a[i] > b[j]);
    }

    private int[] maxArray(int[] nums, int k) {
        int n = nums.length;
        int[] ans = new int[k];
        for (int i = 0, j = 0; i < n; i++) { // i for nums, j for ans while (n - i + j > k && j > 0 && nums[i] > ans[j - 1]) j--; // mimic a stack pop
            if (j < k) ans[j++] = nums[i]; // mimic a stack push
        }
        return ans;
    }

有几点需要注意
1.第5行,i从max(0, k-len2)开始。i代表需要从array1构建的max number的位数,需要从0开始,一直算到k的情况,这样array2就从k位一直构建到0位。但是有一种情况array1不能从0位开始,只能构建k-len2位,这种情况是k=len1+len2,刚好两个array的长度加一起就是k,那两个array都不能去掉任何数字,最后结果就是直接把两个array merge到一起。从数学的角度,i需要满足
i <= k
i <= len1
k – i <= len2 => i >= k – len2
i >= 0

2.第23行greater这个function,第一次没想到要写这个,然后在主function里重复使用。是失败后才觉得这样写比较concise的。

3.第35行(应该缩紧,wordpress的格式不知道怎么回事就是调不好)while的条件:新遇到的数字如果大于stack最上面的数字,而且array剩下的数字还够的话,就要pop stack最上面的数字,然后再push新数字。计算是否array剩下的数字还够:i和n是数字array的指针和总长度,j是结果数组的指针和总长度,所以当n – i <= k – j的时候,无论如何不能再pop了,所以pop的条件是n – i + j > k.

4.time complexity: for 循环中call了两个maxArray,都是O(m+n), 但merge在worst case是O((m+n)^2),即如果merge两个数组总是遇到相同的数字,到最后一位才能分出大小,就需要每一位上check剩余所有数字。另,for loop的循环次数i最大取到k,k即是m+n,所以总体time complexity是O((m+n)^3)。分析过程中发现,如果把merge的复杂度降下来,会有很大帮助。

[LC 174]. Dungeon Game

开始尝试从左到右从上到下记录消耗掉点的最小值,结果陷入了无解。
[-2, -3, 3]
[-5, -10, 1]
[10, 30, -5]
应该从-2 –> -3 –> 3 –> 1 –> -5这条路径走,途中最大的消耗在最后一点(2,2)处,为-6,一共需要7点。路过30这条路虽然到最后需要的点数很少,但开始,例如-2 –> -5这一步消耗点就为-7,需要8点health。所以认为是在每一点算total cost的时候,取上面或左面最大cost最小的那个,一直算到右下最后一点,就可以知道可能用到的最小cost。

然后以下例子就不对了
[1, -3, 3]
[0, -2, 0]
[-3,-3,-3]
算到(1,2)这个位置时,total cost的情况是这样的:
[1, -2, 1]
[1, -1, X]
[X, X, X]
最大cost的情况是这样的:
[1, -2, -2]
[1, -1, X]
[X, X, X]
对(1,2)这点来说,上面来的一路最大cost是-2,左面一路最大cost是-1,所以选择左面一路似乎比较好,这样total cost最终是
[1, -2, 1]
[1, -1,-1]
[-2,-4,-4]
最终的cost是-4,需要5点health。但如果当初选择上面一路,(1,2)点total cost是1,最终点事-2,只需要3点health。所以选择最大cost最小的路径不一定得到正解,因为后面会因为这个选择产生更大的cost,但当初选择的时候并不知道。

这种情况出现的时候就应该意识到,需要倒序算出所需的最小cost。

用一个2D数组记录所需的最小health。在最终点的时候,需要health[m-1][n-1] + dungeon[m-1][n-1] >= 1, health[m-1][n-1] >= 1-dungeon[m-1][n-1]。注意所有的health[i][j]最少为1,如果小于1,证明在之前上一步就已经死了。所以,

health[m-1][n-1] = max(1, 1-dungeon[m-1][n-1])

其他的点health[i][j],需要health[i][j] + dungeon[i][j] >= min(health[i+1][j], health[i-1][j]),即算上初始的health,在算上进入(i,j)这间屋需要消耗的health,需要至少能到达右面和下面两个中需要health比较小的一个。所以

health[i][j] = max(1, min(health[i+1][j], health[i][j+1]) – dungeon[i][j])

如果i+1或j+1超出了范围,在调整上面公式,去掉health[i+1][j]或health[i][j+1].最后health[0][0]就是答案。

[LC 418]. Sentence Screen Fitting

首先用最intuitive的方法做了一下,就是一个词一个词看是否能fit当前row,然后记录写下了几个sentence。得到了正确答案,但是time limit exceed.

然后看了论坛,明白了思路:不是一个词一个词往row里面装,而是假设string是无限循环下去的,记录所有row走完会move到哪里。最后start指针的值相当于一共在screen上有多少字符具体说包含以下步骤:
1. 先把sentence连起来,然后摊平。例如:[“abc”, “de”, “f”],连成sentence是”abc de f “,设想这个sentence无限循环,就是”abc de f abc de f abc de f abc…”
2. 用一个pointer记录每一行的start,每多一个row,把pointer往后移动cols个。
3. 移动pointer时两种情况需要处理一下:(1) 一行的开头刚好是space,start指针直接+1,即remove一个space,(2)一行的开头刚好是一个word的中间,start需要退回到该word的开头,即在上一行增加一些space。

    public int wordsTyping(String[] sentence, int rows, int cols) {
        if (sentence == null || sentence.length == 0 || rows == 0 || cols == 0) return 0;
        String s = String.join(" ", sentence) + " ";
        int len = s.length();
        int start = 0;
        for (int i = 0; i < rows; i++) {
            start += cols;
            if (s.charAt(start % len) == ' ') {
                start++;
            } else {
                while (start > 0 && s.charAt((start - 1) % len) != ' ') {
                    start--;
                }
            }
        }
        
        return start / len;
    }

[LC 467].Unique Substrings in Wraparound String

问题:Consider the string s to be the infinite wraparound string of “abcdefghijklmnopqrstuvwxyz”, so s will look like this: “…zabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcd….”.

Now we have another string p. Your job is to find out how many unique non-empty substrings of p are present in s. In particular, your input is the string p and you need to output the number of different non-empty substrings of p in the string s.

Note: p consists of only lowercase English letters and the size of p might be over 10000.

一道简单的DP,code也不长,但关键是想明白是用DP做的。

从一个例子开始:”wyzas”。开始发现,这段string可以分成三段连续的substring,”w”, “yza”, “s”, 首尾只有一个substring,中间有3+2+1 = 6个,”y”, “z”, “a”, “yz”, “za”, “yza”。那么是不是找到所有这样的分段,加在一起就是答案呢?不是。因为还有重合的情况,例如 “xyzyz”, 两端连续的分别是”xyz”, “yz”,第二段是第一段的substring,所以并不能为总和贡献新的unique substring。此时又陷入了沉思-____-

解决问题关键的点是:unique substring的总和,即答案,是以字母’a’ – ‘z’结尾的max substring的和。例如在”yza”中:
以”y”结尾的max substring长度是1,对应找到的unique substring是”y”;
以”z”结尾的max substring长度是2,对应找到的unique substring是”z”和”yz”
以”a”结尾的max substring长度是3,对应找到的unique substring是”a”, “za”, 和”yza”
在第二个例子”xyzyz”中:
以”x”结尾的max substring长度是1,对应找到的unique substring是”x”
以”y”结尾的max substring长度是2,对应找到的unique substring是”y”和”xy”
以”z”结尾的max substring长度是3,在后半段连续substring中找到的max长度是2,但小于3,所以总体max substring的长度是3.

    public int findSubstringInWraproundString(String p) {
        if (p.length() < 2) return p.length();
        int[] length = new int[26];
        int len = 0;
        for (int i = 0; i < p.length(); i++) {
            if (i == 0 || p.charAt(i) - 'a' == (p.charAt(i-1) - 'a' + 1) % 26) {
                len++;
            } else {
                len = 1;
            }
            length[p.charAt(i) - 'a'] = Math.max(len, length[p.charAt(i) - 'a']);
        }
        int sum = 0;
        for (int i = 0; i < 26; i++) {
            sum += length[i];
        }
        return sum;
    }

[LC 312]. Burst Balloons

首先想到用图来表示一下这个过程:一共n步,第i步从n-i个气球中戳一个,例如[3,1,5,8]
start

|

| burst 0 | 1 | 2 |3
… coin: 315=15 …… coin: 40


| 0 |2 |3 | 0 | 1 |2
coin: 135 coin: 3
————- ……
| 2 |3
coin: 40 coin: 40


| 3 | 2
coin : 8 coin : 5

直接计算,time complexity是O(n!),但是发现一个规律:剩下的所有气球可以得到的max coin和已经burst的无关。例如,在[3,1,5,8]这个例子中,先burst3或1,剩下的都是[5,8],这个subarray得到的maxcoin和之前3和1哪个先burst无关,都是相同的,所以没必要重复计算,可以记录下来。

然后得到提示用divide and conquer,每次burst第i个,然后分成i以左和以右,两个subproblem。问题是左右虽然range虽然确定,但range的首位相邻的数字不确定,而且在算coin时需要。例如[3,1,5,8],先burst 1,左边剩下[3],3的左边是1右边变成了5;再burst 5,左边还是[3],3的左边还是1,但右边变成了8。这样虽然可以在recursion的时候,给function加上int head, int tail两个变量,但是会导致dp或者memoization不好实现。

然后是关键一步:换一种方法分割subproblem,采用top-down的思路 (reverse of bottom-up, which is above),若最后一个burst的是第i个,那么左右两个部分的head和tail都是确定的。例如[3,1,5,8],最后burst 1,左边是[3], 右边是[5,8], 无论倒数第二个burst哪个,head和tail都是1和1.
left             right
[ 1, 3,1,5,8, 1 ]
burst(int[] nums, int left, int right, int[][] dp) 是这个recursive function
其中:
for (i from left+1 to right-1) // last burst the ith balloon in the subproblem
ans = max(ans,
burst(nums, left, i, dp) +
burst(nums, i, right, dp) +
nums[left]nums[i]nums[right]) // head and tail for ith are known

[Summary] Knapsack problems

变形的背包问题是DP中的一类典型题。例如[LC 474]. Ones and Zeroes. Given the restriction that m 0s and n 1s are available, and a string array like [“01”, “0001”, “1100010”,…], calculate the max number of strings that you can represent under the restriction. 对每个string,只有选择或不选择两个可能,是0/1背包问题。如果只有0个数的限制,或只有1个数的限制,greedy就可以做。如果每个string可以拆分,就像0/1背包问题中每个item可以拆分一样,那也可以用greedy做。但这个问题,只能用dp做。

  • 需要keep track的变量:1的个数和0的个数。所以存(m+1)*(n+1) matrix, dp[i][j]=no. of string when i 0s and j 1s are allowed
  • 需要update的公式:dp[i][j] = max(dp[i][j], dp[i-count0][j-count1])
    不take当前string take当前string
  • 循环是倒序的,见code。采用正序还是倒序,糊涂的时候用一个例子手动填写dp table试试。
    public int findMaxForm(String[] strs, int m, int n) {
        int[][] dp = new int[m+1][n+1];
        for (String str : strs) {
            int[] count = binCount(str);
            if (count[0] > m || count[1] > n) continue;
            for (int i = m; i >= count[0]; i--) { // 倒序
                for (int j = n; j >= count[1]; j--) { // 倒序
                    dp[i][j] = Math.max(dp[i][j], dp[i-count[0]][j-count[1]] + 1);
                }
            }
        }
        
        return dp[m][n];
    }
    
    private int[] binCount(String s) {
        int[] count = new int[2];
        count[0] = s.replace("1","").length();
        count[1] = s.replace("0","").length();
        return count;
    }

[LC 309]. Best Time to Buy and Sell Stock with Cooldown

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)

在决定是否sell的时候,想到sell了之后要cool down,不能买进,所以global最优解可能并不是一直track local的最优解能得到的。例如[1,3,4,0,2],在3处sell了,0处还可以买进,总利润4。在4处sell,就不能再获得新的利润了,总利润是3. 所以比较明显用DP来做。

存什么样的中间结果呢?想到了三种transection各存一个array。这时,就应该放弃具体例子,写出三个transection各自的公式。
buy[i] = max(rest[i-1]-price, buy[i-1])
sell[i] = max(buy[i-1]+price, sell[i-1])
rest[i] = max(sell[i-1], buy[i-1], rest[i-1])

注意到buy[i] <= rest[i], rest[i] <= sell[i],所以rest[i] = sell[i-1]. 所以公式变为:
buy[i] = max(sell[i-2] – price, buy[i-1])
sell[i] = max(buy[i-1] + price, sell[i-1])

[LC 416]. Partition Equal Subset Sum

背包问题,学习ing。一个array,问是否能分成和相等的两个部分,例如[1,5,7,11]可分为[1,11]和[5,7]所以是true,[1,2,5]是false。可以变换成:是否在array能找到几个数,他们的和为总和的一半。可以用2D数组做,略过。看看用1D数组做的:

    public boolean canPartition(int[] nums) {
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        if (sum % 2 != 0) return false;
        sum = sum / 2; 
        ///////////////////
        boolean[] dp = new boolean[sum+1];
        dp[0] = true;
        for (int num : nums) {
            for (int i = sum; i >= 0; i--) {
                if (i >= num) {
                    dp[i] = dp[i] || dp[i-num];
                }
            }
        }
        return dp[sum];
    }

分割线以上都没什么好说的。以下注意一个地方:i 从 sum 减少一直到0,而非从0增加到sum。反过来就错了。从意义上理解一下为什么。每次来一个新的num,要看选择或不选择这个num,是否可以使和为sum,如果i从下到大增加,可能会让dp中所有的元素都为true。看一个例子:
array: [1,2,5], sum = 8, sum = sum/2 = 4, dp has length sum+1 = 5.
i–的时候,dp的变化:
0 1 2 3 4
num = 1, dp = [T, T, F, F, F] (given number 1, we can get sum = 1)
num = 2, dp = [T, T, T, T, F] (given 2, get 2 by not taking 1, 3 by taking 1)
num = 5, dp = [T, T, T, T, F] (when i = 4, i < num, so nothing changes)

i++的时候,dp的变化
0 1 2 3 4
num = 1, dp = [T, T, T, T, T] (means when given num = 1, we can construct sum = 1, and 2 by taking one more 1, and 3 by taking one more 1, and 4 by taking one more 1. The procedure is impossible. We can take 1 once.)

[LC 322]. Coin Change

一个典型的DP问题。两种做法,iterative和recursive。都需要一个int[] dp = new int[amount+1],来存sum从1到amount所需要coin的最小个数。

Iterative: bottom up, 1->amount

    public int coinChange(int[] coins, int amount) {
        if (amount < 1) return 0;
        int[] dp = new int[amount+1];
        for (int sum = 1; sum <= amount; sum++){
            int min = -1;
            for (int coin : coins) {
                if (sum >= coin && dp[sum - coin] != -1) {
                    int count = dp[sum - coin] + 1;
                    min = (min == -1) ? count : Math.min(min, count);
                }
            }
            dp[sum] = min;
        }
        return dp[amount];
    }

Recursive: top down, amount->1

    public int coinChange(int[] coins, int amount) {
        if (amount < 1) return 0;
        return helper(coins, amount, new int[amount]);
    }
    
    private int helper(int[] coins, int rem, int[] count) {
        if (rem < 0) return -1;
        if (rem == 0) return 0;
        if (count[rem - 1] != 0) return count[rem - 1];
        int min = Integer.MAX_VALUE;
        for (int coin : coins) {
            int res = helper(coins, rem - coin, count);
            if (res >= 0 && res < min) {
                min = res+1;
            }
        }
        count[rem - 1] = (min == Integer.MAX_VALUE) ? -1 : min;
        return count[rem - 1];
    }