把原本複雜的問題分解為相對簡單的子問題，通常適用於有重疊子問題的情況，可以透過儲存子問題的答案減少之後處理複雜問題的時間。

Rod Cutting Problem

有一根長度為 L 的棒子，以及價格表 v[i] 代表 長度為 i 的棒子的價值，找出一種切割方案，使得切割後的棒子價值總和最大。

建立一個 vector 來儲存長度為 i 的棒子切割後的最大總價值。

1
2
3
4
5
6
7
8
9
10
11
int rodCutting(int L, vector<int> v){
    vector<int> dp(L + 1, 0);
    for(int i = 1; i <= n; i++){
        int m = 0; 
        for(int j = 1; j <= i; j++){
          m = max(m, v[j] + dp[i - j]);
        }
        dp[i] = m;
    }
    return dp[L];
}

陣列的更新是由較短的長度開始往後更新，之後較大的值就可以透過前面已有的陣列值進行判斷。

最大子數列

Kadane’s Algorithm

最長遞增子序列

給定一個陣列，最長遞增子序列是其一子序列，其中的每個元素值為遞增。

Longest Increasing Subsequence (LIS)

  • 求出最長遞增子序列的長度。

建立一個 vector 來儲存以 arr[i] 為結尾的 LIS 長度。

1
2
3
4
5
6
7
8
9
10
11
int LIS(vector<int> arr){
    vector<int> dp(arr.size(), 1); //初始為1
    int m = 0;
    for(int i = 0; i < arr.size(); i++){
        for(int j = 0; j < i; j++){
          if(arr[j] < arr[i]) dp[i] = max(dp[i], dp[j] + 1);
        }
        m = max(m, dp[i]);
    }
    return m;
}

Weighted Longest Increasing Subsequence

  • 每個 arr[i] 有其對應的權重 w[i]。
  • 求權重和最大的遞增子序列之長度。

建立一個 vector 來儲存以 arr[i] 為結尾的 weightedLIS 權重。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int weightedLIS(vector<int> arr, vector<int> w){
    vector<int> dp(arr.size());
    for(int i = 0; i < arr.size(); i++){
      dp[i] = w[i]; //初始化為權重
    }
    int m = 0;
    for(int i = 0; i < arr.size(); i++){
        for(int j = 0; j < i; j++){
          if(arr[j] < arr[i]) dp[i] = max(dp[i], dp[j] + w[i]);
        }
        m = max(m, dp[i]);
    }
    return m;
}

最長共同子序列

求出兩個序列中最長的共同子序列 Longest Common Subsequence (LCS) 之長度。

建立一個二維 vector dp[i][j] 來儲存 v1 前 i 個元素 與 v2 前 j 個元素 的 LCS 長度。

1
2
3
4
5
6
7
8
9
10
int LCS(vector<int> v1, vector<int> v2){
  vector<vector<int>> dp(v1.size() + 1, vector<int>(v2.size() + 1, 0));
	for(int i = 1; i <= v1.size(); i++){
		for(int j = 1; j <= v2.size(); j++){
			if(v1[i - 1] == v2[j - 1]) dp[i][j] = dp[i-1][j-1] + 1;
			else dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
    }
  }
	return dp[v1.size()][v2.size()];
}

編輯距離

兩個字串之間，由一個轉成另一個所需的最少編輯操作次數。

萊文斯坦距離 Levenshtein distance

允許的編輯操作：

  • 將一個字符替換成另一個字符
  • 插入一個字符
  • 刪除一個字符

建立一個二維 vector dp[i][j] 來儲存 str1 前 i 個元素 與 str2 前 j 個元素 之間的萊文斯坦距離。

1
2
3
4
5
6
7
8
9
10
11
12
int editDistance(string str1, string str2){
  vector<vector<int>> dp(str1.size() + 1, vector<int>(str2.size() + 1, 0));
	for(int i = 0; i <= str1.size(); i++){
		for(int j = 0; j <= str2.size(); j++){
      if(i == 0) dp[i][j] = j;
      else if(j == 0) dp[i][j] = i;
      else if(str1[i - 1] == str2[j - 1]) dp[i][j] = dp[i - 1][j - 1];
      else dp[i][j] = 1 + min({dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]});
    }
  }
	return dp[str1.size()][str2.size()];
}

LCS 距離

允許的編輯操作：

  • 插入一個字符
  • 刪除一個字符

矩陣鏈乘積

兩個矩陣分別為 a × b 與 b × c，則將兩者相乘需要 O(abc) 的時間，當我們有一長串的矩陣 (matrix chain) 需要相乘時，可以選擇相乘的順序，目標是求出最短所需要的時間。

建立一個二維 vector dp[i][j] 來儲存 第 i 個矩陣 至 第 j 個矩陣 之間最小的矩陣鏈乘積，外部的兩個迴圈將矩陣之間的距離由小到大進行遍歷，第三個迴圈是對範圍內的分割點進行遍歷。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int matrixChainMultiplication(vector<int> r, vector<int> c){
  vector<vector<int>> dp(r.size(), vector<int>(r.size(), INT_MAX));
  for(int i = 0; i < r.size(); i++){
    dp[i][i] = 0;
  }
	for(int len = 1; len < r.size(); len++){
		for(int i = 0; i + len < r.size(); i++){
      int k = i + len;
      for(int j = i; j < k; j++){ //遍歷分割點
        dp[i][k] = min(dp[i][k], dp[i][j] + dp[j+1][k] + r[i] * c[j] * c[k]);
      }
    }
  }
	return dp[0][r.size() - 1];
}

背包問題

每種物品有其對應的價值 v[i] 與重量 w[i]，將物品塞入一個有重量限制 W 的背包中，並盡量使背包中物品的總價值最大。

分數背包

  • 物品可以切割，可以只放部分物品進入背包。
    利用貪心法，每次從剩餘物品中找單位價值 v[i]/w[i] 最大者，並將其盡可能地塞入背包中，直到背包滿了為止。

0/1 背包問題

  • 每種物品只有一個。
  • 物品無法切割，只能選擇是否放入背包 (0/1)。

建立一個 vector 來儲存在背包重量為 i 時的最大價值。

1
2
3
4
5
6
7
8
9
int knapsack(vector<int> v, vector<int> w, int W){
  vector<int> dp(W + 1, 0);
	for(int i = 0; i < v.size(); i++){
    for(int j = W; j >= w[i]; j--){ //反向
      dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
    }
  }
	return dp[w];
}

第二個迴圈中變數 j 的值是由陣列的尾端開始，是為了避免同一個物品放入背包中兩次 (避免使用前面已更新的數值來更新後面的值)。

無限背包

  • 每種物品有無限個。
  • 物品無法切割，只能選擇是否放入背包 (需要考慮放入的數量)。

建立一個 vector 來儲存在背包重量為 i 時的最大價值。

1
2
3
4
5
6
7
8
9
int knapsack(vector<int> v, vector<int> w, int W){
  vector<int> dp(W + 1, 0);
	for(int i = 0; i < v.size(); i++){
    for(int j = w[i]; j <= W; j++){ //正向
      dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
    }
  }
	return dp[w];
}

與 0/1背包 不同的是，第二個迴圈中變數 j 的值是由陣列的前端開始，因為無限背包問題中的物品是沒有數量限制的，同一個物品可以有多個存在於背包中。

有限背包

  • 每種物品有限定數量 n[i]。
  • 物品無法切割，只能選擇是否放入背包 (需要考慮放入的數量)。

利用二進位分解，將每種物品的數量 n[i] 分成 1,2,4...2k,n[i]−2k1,2,4...2^k,n[i]-2^k，把每個組別當成一個物品，就可以將問題轉換為 0/1背包問題。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int knapsack(vector<int> v, vector<int> w, vector<int> n, int W){
  vector<int> dp(W + 1, 0);
	for(int i = 0; i < v.size(); i++){
    int m = min(n[i], W / w[i]), k = 1;
    while(m > 0){
      if(k > n) k = n;
      n -= k;
      for(int j = W; j >= w[i] * k; j--){ //反向
        dp[j] = max(dp[j], dp[j - w[i] * k] + v[i] * k);
      }
      k *= 2;
    }
  }
	return dp[w];
}

硬幣問題

Coin Change Problem

給定幾種不同價值的硬幣，求有幾種方式能湊到指定的金額。

建立一個 vector 來儲存金額 i 有幾種湊法，並由小到大進行更新。

1
2
3
4
5
6
7
8
9
10
int coinChange(vector<int> c, int T){
  vector<int> dp(T + 1, 0); //初始化為0
  dp[0] = 1; //0元只有一種湊法
	for(int i = 0; i < c.size(); i++){
    for(int j = c[i]; j <= T; j++){
      dp[j] += dp[j - c[i]];
    }
  }
	return dp[T];
}

Change-Making Problem

給定幾種不同價值的硬幣，求湊到指定的金額所需的最少硬幣數。

建立一個 vector 來儲存湊出金額 i 需要的最少硬幣數，並由小到大進行更新。

1
2
3
4
5
6
7
8
9
10
int changeMaking(vector<int> c, int T){
  vector<int> dp(T + 1, INT_MAX); //初始化為無限
  dp[0] = 0; //0元只需要0個硬幣
	for(int i = 0; i < c.size(); i++){
    for(int j = c[i]; j <= T; j++){
      dp[j] = min(dp[j], dp[j - c[i]] + 1);
    }
  }
	return dp[T];
}