<commit_before>---
layout: post
title: "二叉树高频面试算法"
tags: [算法,DP,面试]
---

### 1.阶梯问题

{% highlight python linenos %}  

class Solution1:
    def upstairs(self,n):
        arr = [0]*(n+1)
        arr[0] = arr[1] = 1
        i = 2
        for i in range(2,n+1):
            arr[i] = arr[i-2] + arr[i-1]
        return arr[i]
# print Solution1().upstairs(5)

{% endhighlight %}

### 2.不重复组合 帕斯卡公式 c(n, m) = c(n-1, m-1) + c(n-1, m)

{% highlight python linenos %}

class Solution2:
    def pascal(self,n,m):
        import numpy as np
        if n==1:return 1
        elif m==1:return n
        arr = np.zeros((n+1,m+1)).astype(np.int32)
        arr[1,:], arr[:,1] = 1, range(n+1)
        for i in range(2,n+1):
            for j in range(2,m+1):
                arr[i][j] = arr[i-1][j-1] + arr[i-1][j] if i>j else 1
        return arr[n][m]
# print Solution2().pascal(5,4)

{% endhighlight %}

### 3.汉诺塔

{% highlight python linenos %}

#有三根杆子A，B，C。A杆上有N个(N>1)穿孔圆环，盘的尺寸由下到上依次变小。至少要移动多少次能使圆盘按大小顺序移到C杆
# 递推 f(n) = f(n-1) + 1 + f(n-1)  请思考为什么！
class Solution3:
    def hanoi(self,n):
        arr = [0] * (n+1)
        for i in range(1,n+1):
            arr[i] = 2*arr[i-1]+1
        return arr[n]
# print Solution3().hanoi(5)

{% endhighlight %}

### 4.樓梯路線（ Staircase Walk ）

{% highlight python linenos %}

#計數問題。一個方格棋盤，從左上角走到右下角，每次只能往右走一格或者往下走一格。請問有幾種走法？
class Solution4_1:
    def walk(self,N):
        import numpy as np
        arr = np.zeros((N,N)).astype(np.int32)
        arr[0,:] = arr[:,0] = 1
        for i in range(1,N):
            for j in range(1,N):
                arr[i][j] = arr[i-1][j] + arr[i][j-1]
        return arr[N-1][N-1]
# print Solution4_1().walk(7)

class Solution4_2:
    def walk(self,N):
        arr = [1]*N
        for i in range(1,N):
            for j in range(1,N):
                arr[j] += arr[j-1]
        return arr[N-1]
# print Solution4_2().walk(7)

{% endhighlight %}

### 5.樓梯路線（ Staircase Walk ）

{% highlight python linenos %}

#極值問題。動態規劃的問題，可以分為「計數問題」和「極值問題」。方才介紹「計數問題」，現在介紹「極值問題」。
class Solution5:
    def walk(self,case):
        dist = [ [0]*8 for i in range(8) ]
        for i in range(8):
            for j in range(8):
                if i==0:dist[0][j] = dist[0][j-1] + case[0][j] if j else case[0][0]
                elif j==0:dist[i][0] = dist[i-1][0] + case[i][0]
                else:dist[i][j] = min(dist[i-1][j],dist[i][j-1]) + case[i][j]
        return dist[len(case)-1][len(case)-1]
case = [[0,1,3,2,3,4,5,2],
        [4,2,1,4,6,2,0,3],
        [1,9,9,9,9,9,9,1],
        [8,7,-3,2,1,-2,1,3],
        [9,8,7,0,1,2,7,3],
        [-3,2,2,3,1,-3,1,9],
        [4,5,4,0,4,5,4,5],
        [9,8,7,6,5,4,3,2]]
# print Solution5().walk(case)

{% endhighlight %}

### 6.矩陣相乘次序（ Matrix Chain Multiplication ）

{% highlight python linenos %}

class Solution6:
    def matrix(self):
        row = [4,3,6,2,3]
        col = [3,6,2,3,4]
        f  = [[1e9]*5 for i in range(5)]
        for i in range(5):f[i][i] = 0
        for k in range(1,5):
            for i in range(k-1,-1,-1):
                for j in range(k-1,i-1,-1):
                    f[i][k] = min(f[i][k],f[i][j]+f[j+1][k]+row[i]*col[j]*col[k])
        return f[0][4]
# print Solution6().matrix()

class Solution6:
    def matrix(self):
        row = [4,3,6,2,3]
        col = [3,6,2,3,4]
        f  = [[1e9]*5 for i in range(5)]
        for i in range(5):f[i][i] = 0
        for k in range(1,5):
            for i in range(k-1,-1,-1):
                for j in range(k-1,i-1,-1):
                    f[i][k] = min(f[i][k],f[i][j]+f[j+1][k]+row[i]*col[j]*col[k])
        return f[0][2]
# print Solution6().matrix()

{% endhighlight %}

### 7.Longest Increasing Subsequence

### 8.如何存储状态。
#bitset 是一個二進位數字，每一個 bit 分別代表每一件東西， 1 代表開啟， 0 代表關閉。
# 例如現在有十個燈泡，編號設定為零到九，其中第零個、第三個、第九個燈泡是亮的，
# 剩下來的燈泡是暗的。我們用一個 10 bit 的二進位數字 1000001001 ，表示這十個燈泡的亮暗狀態。
# 建立一個大小為 2^10 的陣列，便囊括了所有可能的狀態。陣列的每一格，就代表一種燈泡開關的狀態。
# int array[1<<10];

### 9.以線相連的兩物，可以配對在一起。求最大配對數目暨配對方式。

{% highlight python linenos %}

# 题目描述见 http://www.csie.ntnu.edu.tw/~u91029/DPBitset2.png
import sys
sys.setrecursionlimit(1<<20)
class Solution9:
    def connect(self,n):
        def dp_func(s):
            if s==0:return 0
            if self.ok[s]:return self.dp[s]
            for i in range(10):
                for j in range(i+1,10):
                    if s & ((1<<i) | (1<<j)):
                        ss = s ^ (1<<i) ^ (1<<j)
                        self.dp[s] = max(self.dp[s],dp_func(ss)+self.adj[i][j])
            self.ok[s] = True
            return self.dp[s]
        self.adj = [[1, 0, 1, 0, 1, 0, 0, 0, 0, 0],
                    [0, 1, 1, 3, 0, 0, 0, 0, 0, 0],
                    [0, 1, 0, 1, 0, 0, 0, 1, 0, 0],
                    [1, 0, 0, 0, 1, 1, 0, 0, 0, 0],
                    [0, 0, 0, 0, 1, 1, 1, 0, 0, 0],
                    [0, 0, 0, 0, 0, 1, 1, 0, 0, 0],
                    [0, 0, 0, 0, 0, 0, 0, 1, 1, 0],
                    [0, 0, 0, 0, 0, 0, 0, 0, 1, 1]]
        self.ok, self.dp = [False] * (1 << 10), [0] * (1 << 10)
        return dp_func(1<<n-1)
# print Solution9().connect(10)

{% endhighlight %}

### 10.Hamilton Path 找到一条路径，刚好每一个点都去过一次。有可能找不到。

{% highlight python linenos %}

# http://www.csie.ntnu.edu.tw/~u91029/DPBitset3.png
class Solution10:
    def hanilton(self):
        self.adj = [  [True,True,True,False,False,False,False],
                      [True,True,False,True,False,False,True],
                      [True,False,True,False,True,True,False],
                      [False,True,False,True,False,True,True],
                      [False,False,True,False,True,True,False],
                      [False,False,True,True,True,True,True],
                      [False,True,False,True,False,True,True]]
        self.dp = [[False]*7 for i in range(1<<7)]
        # ok[s][j]记录s情况下从j起始这种情况是否已经讨论过
        self.ok = [[False]*7 for i in range(1<<7)]
        def dp_func(s,size,j):
            if size==1:return True
            if(self.ok[s][j]):return self.dp[s][j]
            self.ok[s][j] = True
            for i in range(7):
                if i!=j and s & (1<<i):
                    if dp_func(s^(1<<j),size-1,i) and self.adj[i][j]:
                        self.dp[s][j] = True
                        return self.dp[s][j]
            self.dp[s][j] = False
            return self.dp[s][j]
        for i in range(7):
            if dp_func((1<<7)-1,7,i):
                return True
        return False
# print Solution10().hanilton()

{% endhighlight %}

关于DP算法的学习，可移步[此博客](http://www.csie.ntnu.edu.tw/~u91029/DynamicProgramming.html)<commit_msg>Signed-off-by: <NAME> <<NAME>><commit_after>---
layout: post
title: "DP十例题"
tags: [算法,DP,面试]
---

### 1.阶梯问题

{% highlight python linenos %}  

class Solution1:
    def upstairs(self,n):
        arr = [0]*(n+1)
        arr[0] = arr[1] = 1
        i = 2
        for i in range(2,n+1):
            arr[i] = arr[i-2] + arr[i-1]
        return arr[i]
# print Solution1().upstairs(5)

{% endhighlight %}

### 2.不重复组合 帕斯卡公式 c(n, m) = c(n-1, m-1) + c(n-1, m)

{% highlight python linenos %}

class Solution2:
    def pascal(self,n,m):
        import numpy as np
        if n==1:return 1
        elif m==1:return n
        arr = np.zeros((n+1,m+1)).astype(np.int32)
        arr[1,:], arr[:,1] = 1, range(n+1)
        for i in range(2,n+1):
            for j in range(2,m+1):
                arr[i][j] = arr[i-1][j-1] + arr[i-1][j] if i>j else 1
        return arr[n][m]
# print Solution2().pascal(5,4)

{% endhighlight %}

### 3.汉诺塔

{% highlight python linenos %}

#有三根杆子A，B，C。A杆上有N个(N>1)穿孔圆环，盘的尺寸由下到上依次变小。至少要移动多少次能使圆盘按大小顺序移到C杆
# 递推 f(n) = f(n-1) + 1 + f(n-1)  请思考为什么！
class Solution3:
    def hanoi(self,n):
        arr = [0] * (n+1)
        for i in range(1,n+1):
            arr[i] = 2*arr[i-1]+1
        return arr[n]
# print Solution3().hanoi(5)

{% endhighlight %}

### 4.樓梯路線（ Staircase Walk ）

{% highlight python linenos %}

#計數問題。一個方格棋盤，從左上角走到右下角，每次只能往右走一格或者往下走一格。請問有幾種走法？
class Solution4_1:
    def walk(self,N):
        import numpy as np
        arr = np.zeros((N,N)).astype(np.int32)
        arr[0,:] = arr[:,0] = 1
        for i in range(1,N):
            for j in range(1,N):
                arr[i][j] = arr[i-1][j] + arr[i][j-1]
        return arr[N-1][N-1]
# print Solution4_1().walk(7)

class Solution4_2:
    def walk(self,N):
        arr = [1]*N
        for i in range(1,N):
            for j in range(1,N):
                arr[j] += arr[j-1]
        return arr[N-1]
# print Solution4_2().walk(7)

{% endhighlight %}

### 5.樓梯路線（ Staircase Walk ）

{% highlight python linenos %}

#極值問題。動態規劃的問題，可以分為「計數問題」和「極值問題」。方才介紹「計數問題」，現在介紹「極值問題」。
class Solution5:
    def walk(self,case):
        dist = [ [0]*8 for i in range(8) ]
        for i in range(8):
            for j in range(8):
                if i==0:dist[0][j] = dist[0][j-1] + case[0][j] if j else case[0][0]
                elif j==0:dist[i][0] = dist[i-1][0] + case[i][0]
                else:dist[i][j] = min(dist[i-1][j],dist[i][j-1]) + case[i][j]
        return dist[len(case)-1][len(case)-1]
case = [[0,1,3,2,3,4,5,2],
        [4,2,1,4,6,2,0,3],
        [1,9,9,9,9,9,9,1],
        [8,7,-3,2,1,-2,1,3],
        [9,8,7,0,1,2,7,3],
        [-3,2,2,3,1,-3,1,9],
        [4,5,4,0,4,5,4,5],
        [9,8,7,6,5,4,3,2]]
# print Solution5().walk(case)

{% endhighlight %}

### 6.矩陣相乘次序（ Matrix Chain Multiplication ）

{% highlight python linenos %}

class Solution6:
    def matrix(self):
        row = [4,3,6,2,3]
        col = [3,6,2,3,4]
        f  = [[1e9]*5 for i in range(5)]
        for i in range(5):f[i][i] = 0
        for k in range(1,5):
            for i in range(k-1,-1,-1):
                for j in range(k-1,i-1,-1):
                    f[i][k] = min(f[i][k],f[i][j]+f[j+1][k]+row[i]*col[j]*col[k])
        return f[0][4]
# print Solution6().matrix()

class Solution6:
    def matrix(self):
        row = [4,3,6,2,3]
        col = [3,6,2,3,4]
        f  = [[1e9]*5 for i in range(5)]
        for i in range(5):f[i][i] = 0
        for k in range(1,5):
            for i in range(k-1,-1,-1):
                for j in range(k-1,i-1,-1):
                    f[i][k] = min(f[i][k],f[i][j]+f[j+1][k]+row[i]*col[j]*col[k])
        return f[0][2]
# print Solution6().matrix()

{% endhighlight %}

### 7.Longest Increasing Subsequence

### 8.如何存储状态。
#bitset 是一個二進位數字，每一個 bit 分別代表每一件東西， 1 代表開啟， 0 代表關閉。
# 例如現在有十個燈泡，編號設定為零到九，其中第零個、第三個、第九個燈泡是亮的，
# 剩下來的燈泡是暗的。我們用一個 10 bit 的二進位數字 1000001001 ，表示這十個燈泡的亮暗狀態。
# 建立一個大小為 2^10 的陣列，便囊括了所有可能的狀態。陣列的每一格，就代表一種燈泡開關的狀態。
# int array[1<<10];

### 9.以線相連的兩物，可以配對在一起。求最大配對數目暨配對方式。

{% highlight python linenos %}

# 题目描述见 http://www.csie.ntnu.edu.tw/~u91029/DPBitset2.png
import sys
sys.setrecursionlimit(1<<20)
class Solution9:
    def connect(self,n):
        def dp_func(s):
            if s==0:return 0
            if self.ok[s]:return self.dp[s]
            for i in range(10):
                for j in range(i+1,10):
                    if s & ((1<<i) | (1<<j)):
                        ss = s ^ (1<<i) ^ (1<<j)
                        self.dp[s] = max(self.dp[s],dp_func(ss)+self.adj[i][j])
            self.ok[s] = True
            return self.dp[s]
        self.adj = [[1, 0, 1, 0, 1, 0, 0, 0, 0, 0],
                    [0, 1, 1, 3, 0, 0, 0, 0, 0, 0],
                    [0, 1, 0, 1, 0, 0, 0, 1, 0, 0],
                    [1, 0, 0, 0, 1, 1, 0, 0, 0, 0],
                    [0, 0, 0, 0, 1, 1, 1, 0, 0, 0],
                    [0, 0, 0, 0, 0, 1, 1, 0, 0, 0],
                    [0, 0, 0, 0, 0, 0, 0, 1, 1, 0],
                    [0, 0, 0, 0, 0, 0, 0, 0, 1, 1]]
        self.ok, self.dp = [False] * (1 << 10), [0] * (1 << 10)
        return dp_func(1<<n-1)
# print Solution9().connect(10)

{% endhighlight %}

### 10.Hamilton Path 找到一条路径，刚好每一个点都去过一次。有可能找不到。

{% highlight python linenos %}

# http://www.csie.ntnu.edu.tw/~u91029/DPBitset3.png
class Solution10:
    def hanilton(self):
        self.adj = [  [True,True,True,False,False,False,False],
                      [True,True,False,True,False,False,True],
                      [True,False,True,False,True,True,False],
                      [False,True,False,True,False,True,True],
                      [False,False,True,False,True,True,False],
                      [False,False,True,True,True,True,True],
                      [False,True,False,True,False,True,True]]
        self.dp = [[False]*7 for i in range(1<<7)]
        # ok[s][j]记录s情况下从j起始这种情况是否已经讨论过
        self.ok = [[False]*7 for i in range(1<<7)]
        def dp_func(s,size,j):
            if size==1:return True
            if(self.ok[s][j]):return self.dp[s][j]
            self.ok[s][j] = True
            for i in range(7):
                if i!=j and s & (1<<i):
                    if dp_func(s^(1<<j),size-1,i) and self.adj[i][j]:
                        self.dp[s][j] = True
                        return self.dp[s][j]
            self.dp[s][j] = False
            return self.dp[s][j]
        for i in range(7):
            if dp_func((1<<7)-1,7,i):
                return True
        return False
# print Solution10().hanilton()

{% endhighlight %}

关于DP算法的学习，可移步[此博客](http://www.csie.ntnu.edu.tw/~u91029/DynamicProgramming.html)
{'fraction_non_alphanumeric': 0.19588884659307196, 'fraction_numerical': 0.06075371145793681, 'mean_word_length': 1.995667046750285, 'pattern_counts': {'":': 0, '<': 62, '<?xml version=': 0, '>': 10, 'https://': 0, 'lorem ipsum': 0, 'www.': 6, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '6415993', 'n_tokens_mistral': 6412, 'n_tokens_neox': 6179, 'n_words': 1087}