# Week2 - Dynamic Programming

###### tags: `Leetcode`

## 5. Longest Palindromic Substring
思路：定義指針 $i, j$ 分別代表子字串的起始與終止位置，並定義陣列 $table$，起始位置為 $i$ 終止位置為 $j$ 的子字串為對稱的，$table[i][j]=True$，否則，$table[i][j]=False$，由此可知，陣列 $table$ 滿足下列性質：
+ $table[i][i] = 1$。
+ 若 $s[i] == s[j]$ 且 $table[i+1][j-1] = True$，則 $table[i][j] = True$。
+ 若 $s[i] == s[j]$ 且 $j == i+1$，則 $table[i][j] = True$。

class Solution:
    def longestPalindrome(self, s: str) -> str:
        l = len(s)
        save_list = [False] * l
        max_length, target_tuple = 0, (-1, -1)
        
        for j in range(l): 
            for i in range(j + 1):
                if i == j or (s[i] == s[j] and (j == i+1 or save_list[i+1])): 
                    save_list[i] = True
                    if j - i + 1 > max_length: 
                        max_length = j - i + 1 
                        target_tuple =  (i, j)
                else: 
                    save_list[i] = False
        return s[target_tuple[0]: target_tuple[1]+1]     

+ Ping-Hsuan's solution

class Solution:
    def longestPalindrome(self, s: str) -> str:
        res = ''
        resLen = 0
        
        for i in range(len(s)):
            # Odd length
            l, r = i, i
            while l >=0 and r < len(s) and s[l] == s[r]:
                if (r-l+1) > resLen:
                    res = s[l:r+1]
                    resLen = r-l+1
                l -= 1
                r += 1
            # Even legnth
            l, r = i, i+1
            while l >= 0 and r < len(s) and s[l] == s[r]:
                if (r-l+1) > resLen:
                    res = s[l:r+1]
                    resLen = r-l+1
                l -= 1
                r += 1 
        return res

+ **Links**
+ https://www.youtube.com/watch?v=ZnzvU03HtYk

## 70. Climbing Stairs
定義函數 $\phi(k)=$ 走 k 步的所有組合。我們知道 $\phi(k)$ 滿足下列性質：
$$ \phi(n)=\left\{
\begin{array}{rcl}
&\phi(n-1) + \phi(n-2)&, & & {n>=2}\\
&1&, & & {n<2}
\end{array} \right. $$

class Solution:
    def climbStairs(self, n: int) -> int:
        ways = [1, 1] 
        for i in range(2, n+1):
            ways.append(ways[i-1] + ways[i-2])
        return ways[-1]

## 64. Minimum Path Sum


class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        last_min_array = [0] * n 
        last_min_array[0] = grid[0][0]
        
        for i in range(1, n):
            last_min_array[i] = last_min_array[i-1] + grid[0][i] 
        
        for i in range(1, m): 
            for j in range(n):
                if j == 0:  
                    last_min_array[j] = last_min_array[0] + grid[i][j]
                else: 
                    last_min_array[j] = min(last_min_array[j-1], last_min_array[j]) + grid[i][j]
                    
        return last_min_array[-1]

## 62. Unique Paths
我們知道所有的組合數滿足 $C^{n+m-2}_{n-1}$ 的公式。


class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        return self.combinatory(m+n-2, min(m,n)-1) 
    
    def combinatory(self, n, k):
        numerator, deniminator = 1, 1
        for i in range(n, n-k, -1): 
            numerator *= i
            
        for i in range(2, k+1): 
            deniminator *= i
        
        return int(numerator/deniminator) 

## 53. Maximum Subarray

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        max_sum, curr_sum = nums[0], 0   
        for ele in nums: 
            curr_sum = curr_sum + ele
            max_sum = max(max_sum, curr_sum)
            if curr_sum < 0: 
                curr_sum = 0 
        return max_sum 

Ping-Hsuan Q: How do we prove this?, how about divide and conquer?

+ **Links**
+ divide and conquer： https://www.youtube.com/watch?v=3GD-3UZGsVI&t

## 63. Unique Paths II

class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
        m, n = len(obstacleGrid), len(obstacleGrid[0])
        last_res = [1 - obstacleGrid[0][0]] * n 
        
        for j in range(1, n):
            last_res[j] =  last_res[j-1] if obstacleGrid[0][j] == 0 else 0
        
        for i in range(1, m): 
            if obstacleGrid[i][0] == 1: 
                last_res[0] = 0 
            for j in range(1, n):
                last_res[j] = last_res[j-1] + last_res[j] if obstacleGrid[i][j] == 0 else 0 
        return last_res[-1]