greedy

*dp.java

516. Longest Palindromic Subsequence
https://leetcode.com/problems/longest-palindromic-subsequence/
https://www.youtube.com/watch?v=v8irqkTcJ6s
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".
  
dp[i][j]: the longest palindromic subsequence's length of substring(i, j), here i, j represent left, right indexes in the string
State transition:
dp[i][j] = dp[i+1][j-1] + 2 if s.charAt(i) == s.charAt(j)
otherwise, dp[i][j] = Math.max(dp[i+1][j], dp[i][j-1])
Initialization: dp[i][i] = 1
  
time complexity O(n^2)
class Solution {
    public int longestPalindromeSubseq(String s) {
        
        int len= s.length();
        int[][] dp = new int[len][len];
        
        for (int i = len - 1; i >= 0; i--) {
            dp[i][i] = 1;
            for (int j  = i+1; j < len; j++) {
                if (s.charAt(i) == s.charAt(j)) 
                    dp[i][j] = dp[i+1][j-1] + 2;
                else 
                    dp[i][j] = Math.max(dp[i+1][j], dp[i][j-1]);
            }
        }
        
        return dp[0][len-1];

    }
}  

array.py

139. Word Break
https://leetcode.com/problems/word-break/description/
Input: s = "leetcode", wordDict = ["leet", "code"]
Output: true
#------------------------dp---------------------------
N= len(s)
dp = [False for i in range(N+1)]
dp[0] = True
for i in range(1, N+1):
    for j in range(i):
        if dp[j] and s[j:i] in wordDict:    dp[i] = True
if not dp[N]: return []   

140. Word Break II
https://leetcode.com/problems/word-break-ii/description/
Input:
s = "catsanddog"
wordDict = ["cat", "cats", "and", "sand", "dog"]
Output:
[
  "cats and dog",
  "cat sand dog"
]

class Solution(object):
    def wordBreak(self, s, wordDict):
        """
        :type s: str
        :type wordDict: List[str]
        :rtype: List[str]
        """
        #runtime complexity 
        #------------------------dp---------------------------
        N= len(s)
        dp = [False for i in range(N+1)]
        dp[0] = True
        for i in range(1, N+1):
            for j in range(i):
                if dp[j] and s[j:i] in wordDict:    dp[i] = True
        if not dp[N]: return [] 
        #-------------------------dfs-------------------     
        def dfs(i, substr):
            if i<N:
                for j in range(i+1, N+1):
                    if dp[j] and (s[i:j] in wordDict):
                        dfs(j, substr+' '+s[i:j]  if substr else s[i:j])
            else: ans.append(substr)
        ans= []
        dfs(0, '')
        return ans

dp.java

62. Unique Paths
https://leetcode.com/problems/unique-paths/description/
class Solution(object):
    def uniquePaths(self, m, n):
        """
        :type m: int
        :type n: int
        :rtype: int
        """
        #runtime complexity O(m*n)  space complexity O(m*n)
        # dp[m][n]= dp[m-1][n] + dp[m][n-1]
        dp= [ n*[1] for _ in range(m) ]
        for i in range(1, m):
            for j in range(1, n):
                dp[i][j]= dp[i-1][j] + dp[i][j-1]
        
        return dp[m-1][n-1]

63. Unique Paths II
https://leetcode.com/problems/unique-paths-ii/description/
  
  class Solution(object):
    def uniquePathsWithObstacles(self, obstacleGrid):
        """
        :type obstacleGrid: List[List[int]]
        :rtype: int
        """
        # if obstacleGrid[i][j]!=1:   dp[i][j]= dp[i-1][j] + dp[i][j-1]
        #runtime complexity: O(m*n+m+n) space complexity : O(m*n)
        if not obstacleGrid: return 0
        m, n= len(obstacleGrid), len(obstacleGrid[0])
        
        dp= [ n*[0] for _ in range(m) ]
        for i in range(m):  
            if obstacleGrid[i][0]==0:   dp[i][0]= 1
            else: break
  
        for j in range(n):  
            if obstacleGrid[0][j]==0: dp[0][j]= 1
            else: break
        
        for i in range(1, m):
            for j in range(1, n):
                if obstacleGrid[i][j]!=1:   dp[i][j]= dp[i-1][j] + dp[i][j-1]
        
        return dp[m-1][n-1]  
    
741. Cherry Pickup
https://leetcode.com/problems/cherry-pickup/
In a N x N grid representing a field of cherries, each cell is one of three possible integers.
0 means the cell is empty, so you can pass through;
1 means the cell contains a cherry, that you can pick up and pass through;
-1 means the cell contains a thorn that blocks your way.
Your task is to collect maximum number of cherries possible by following the rules below:
Starting at the position (0, 0) and reaching (N-1, N-1) by moving right or down through valid path cells (cells with value 0 or 1);
After reaching (N-1, N-1), returning to (0, 0) by moving left or up through valid path cells;
When passing through a path cell containing a cherry, you pick it up and the cell becomes an empty cell (0);
If there is no valid path between (0, 0) and (N-1, N-1), then no cherries can be collected.
Example 1:
Input: grid =
[[0, 1, -1],
 [1, 0, -1],
 [1, 1,  1]]
Output: 5
Explanation: 
The player started at (0, 0) and went down, down, right right to reach (2, 2).
4 cherries were picked up during this single trip, and the matrix becomes [[0,1,-1],[0,0,-1],[0,0,0]].
Then, the player went left, up, up, left to return home, picking up one more cherry.
The total number of cherries picked up is 5, and this is the maximum possible.
    class Solution {
    public int cherryPickup(int[][] grid) {
        if (grid==null || grid.length==0 || grid[0].length==0) return 0;
        int n=grid.length;
        
        int[][][] dp=new int[n+1][n+1][n+1];
        for (int i=0;i<=n;i++)
            for (int j=0;j<=n;j++)
                Arrays.fill(dp[i][j], -1);
        
        dp[1][1][1]=grid[0][0];
        for (int x1=1;x1<=n;x1++){
            for (int y1=1;y1<=n;y1++){
                for (int x2=1;x2<=n;x2++){
                    int y2=x1+y1-x2;
                    if (dp[x1][y1][x2]>=0 || y2<1 || y2>n || grid[x1-1][y1-1]<0 || grid[x2-1][y2-1]<0) continue;
                    int max1=Math.max(dp[x1-1][y1][x2],   dp[x1][y1-1][x2]);
                    int max2=Math.max(dp[x1-1][y1][x2-1], dp[x1][y1-1][x2-1]);
                    int max=Math.max(max1, max2);
                    if (max==-1) continue;
                    
                    dp[x1][y1][x2]=max+grid[x1-1][y1-1];
                    if (x2!=x1) dp[x1][y1][x2] += grid[x2-1][y2-1];
                }
            }
        }
        return Math.max(0, dp[n][n][n]);
    }
}
    
    

greedy.py

121. Best Time to Buy and Sell Stock
https://leetcode.com/problems/best-time-to-buy-and-sell-stock/description/
Input: [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
             Not 7-1 = 6, as selling price needs to be larger than buying price.
class Solution(object):
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        if not prices: return 0
        
        Min, Max = prices[0], 0
        for price in prices:
            Min = min(Min, price)
            Max= max(Max, price-Min)
        return Max
      
122. Best Time to Buy and Sell Stock II
https://leetcode.com/problems/best-time-to-buy-and-sell-stock-ii/description/
class Solution(object):
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        ans= 0
        for i in range(1,len(prices)):
            if prices[i]>prices[i-1]:
                ans += prices[i]-prices[i-1]
        return ans
      
123. Best Time to Buy and Sell Stock III
https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iii/description/
class Solution(object):
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        if not prices: return 0
        
        Min, profit = prices[0], 0
        dp= []
        for i, price in enumerate(prices):
            Min = min(Min, price)
            profit= max(profit, price-Min)
            dp.append(profit)
        
        ans, profit, Max=0, 0, prices[-1]
        for i in range(len(prices)-1, -1, -1):
            Max= max(Max, prices[i])
            profit= max(profit, Max-prices[i])
            ans= max(ans, dp[i]+profit)
        return ans
      
----------------------------------------------------------------
53. Maximum Subarray
https://leetcode.com/problems/maximum-subarray/description/
class Solution(object):
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        # runtime complexity: O(N) space complexity: O(2)
        N= len(nums)
        
        ans=Sum= float("-inf")
        for i, num in enumerate(nums):
            Sum = max(Sum+num, num)
            ans = max(ans, Sum)
        return ans
      
152. Maximum Product Subarray
https://leetcode.com/problems/maximum-product-subarray/description/
class Solution(object):
    def maxProduct(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        # runtime complexity: O(N) space complexity: O(3)
        N= len(nums)
        ans= nums[0]
        Min=Max= 1
        for i in range(N):
            Max,  Min= max(nums[i], Max*nums[i], Min*nums[i]), min(nums[i], Max*nums[i], Min*nums[i])
            ans = max(ans, Max)
        return ans