DP

2021-06-25

tech

定义

动态规划，一般用于优化问题，解决类似于xx存不存在，有没有，有多少这样的问题。问到具体的方法的时候，需要在动态规划中加些信息来恢复出最佳方案。动态规划的核心思想就是子问题的最优解也是问题的最优解的一部分，同时在求解问题答案的时候，需要多次重复调用子问题，就可以使用记忆化搜索来减少计算，使得计算复杂度下降通常可以达到一个数量级及以上。动态规划求解是要求具有最优子结构的，既是一个问题的最优解可以从子问题的最优解中获取。

动态规划的步骤一般是：

构造最优解的结构
递归定义最优解
将最优解从自顶向下改为自底向上
根据已有的信息构造出最优解

对于具体的类别在这四篇中会谈到：DP1 single sequence, DP 2 two sequence, DP 3 matrix, DP 4 knapsack.

单个序列

Rod cutting: 原始的不用记忆化的时候时间复杂度T(n) = $2^n$，使用归纳法（inductive method）或者根据切割的次数$2^{(n-1)}$ 来计算。

最原始的求解自顶向下的C++实现：这里面的核心是要理解为什么$r_n = max (p_i + r_{n-i})$

int MaxRodCuttingPrice(const vector<int>& price, const int n) {
  if (n <= 0) return 0;
  int max_price = 0;
  for (int i = 1; i <= n; ++i) {
    max_price = max(max_price, MaxRodCuttingPrice(price, n - 1));
  }
  return max_price;
}

加入记忆化搜索之后的，自顶向下：这个时间复杂度使用aggregate analysis比较合适。

int MaxRodCuttingPrice(const vector<int>& price, const int n, vector<int>* max_prices) {
  if (n <= 0) return 0;
  if (*max_prices[n] >= 0) return *max_prices[n];
  
  int max_price = 0;
  for (int i = 1; i <= n; ++i) {
    max_price = max(max_price, price[i] + MaxRodCuttingPrice(price, n - i, max_prices);
  }
  *max_prices[n] = max_price;
  
  return max_price;
}

自底向上的实现：计算复杂度和上面的一样都是$\Theta (n^2)$.

int MaxRodCuttingPrice(vector<int>& price, int n) {
  if (n <= 0) return 0;
  vector<int> max_prices(MIN_INT, price.size());
  max_prices[0] = 0;
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= i; ++j) {
      max_prices[i] = max(max_prices[i], price[j] + max_prices[i - j]);
    }
  }
  return max_prices[n];
}

如果这个题目需要给出最佳的一个切法的话，可以增加一些辅助信息：

vector<int> FindMaxRodCuttingPrice(const vector<int>& price, 
                                   const int n, vector<int>* selection) {
  if (n <= 0) return {};
  
  vector<int> max_prices(n + 1, 0);
  for (int i = 1; i <= n; ++i) {
    int max_price = 0;
    for (int j = 1; j <= i; ++j) {
      if (max_price < max_prices[i - j] + price[j]) {
        max_price = max_prices[i - j] + price[j];
        *selection[i] = j;
      }
    }
    max_prices[i] = max_price;
  }
  return FindBestSolution(selection, n);
}

vector<int> FindBestSolution(const vector<int>& selection, const int n) {
  if (n <= 0) return {};
  vector<int> remain_solution = FindBestSolution(selection, n - selection[n]);
  remain_solution.push_back(selection[n]);
  return remain_solution;
}

变形，如果每次cut是需要付出额外的费用，那么怎么计算最大收益：

int MaxRodCuttingPrice(const vector<int>& price, const int n, const int c) {
  if (n <= 0) return 0;
  vector<int> max_prices(n+1, 0);
  for (int i = 1; i <= n; ++i) {
    int max_price = 0;
    for (int j = 1; j <= i; ++j) {
      const int cur_price = max_prices[i - j] + price[j] - (i == j ? 0:c);
      max_price = max(cur_price, max_price);
    }
    max_prices[i] = max_price;
  }
  return max_price[n];
}

修改递归版本的使得能够返回best solution:

int FindMaxRodCuttingPrice(const vector<int>& price, const int n, 
                            vector<int>* selection, vector<int>* max_prices) {
  if (n <= 0) return;
  if (*max_prices[n] >= 0) return *max_prices[n];
  
  int max_price = 0;
  for (int i = 1; i <= n; ++i) {
    if (max_price < price[i] + FindMaxRodCuttingPrice(n - i, selection, max_prices)) {
      *selection[n] = i;
      max_price = price[i] + FindMaxRodCuttingPrice(n - i, selection, max_prices);
    }
  }
  *max_prices[n] = max_price;
  return max_price;
}

vector<int> FindBestSolution(selection, n); // From the above function.

Matrix chain multiplication: 加括号的次数 $P(n) = \sum_{k=1}^{n-1} P(k)P(n-k) = 2^n$ 是属于卡塔兰数。通过简单的DP即可变为：$O(n^3)$. 状态转移为：$m[i,j] = min {m[i,k] + m[k+1,j] + p_{i-1} p_k p_j}$

int FindMinMatrixChainMultiplication(const vector<int>& matrix_dims, 
                                     vector<int>* split_position) {
  const auto& dims_size = matrix_dims.size() + 1;
  vector<vector<int>> costs(dims_size, vector<int>(dims_size + 1, INT_MAX));
  for (int len = 2; len <= dims_size; ++len) {
    for (int i = 1; i <= dims_size - len + 1; ++i) {
      for (int j = i; j < i + len; ++j) {
        const int cur_cost = costs[i][j] + costs[j+1][i+len-1]
                                + matrix_dims[i-1]*matrix_dims[j]*matrix_dims[i+len-1];
        if (cur_cost < costs[i][i+len-1]) {
          costs[i][i+len-1] = cur_cost;
          split_position[i][i+len-1] = j;
        }
      }
    }
  }
  return costs[1][dims_size];
}

string FindBestSolution(const vector<vector<int>>& split_position, int i, int j) {
  if (i > j) return "";
  if (i == j) return to_string(i);
  string left = FindBestSolution(split_position, i, split_position[i][j]);
  string right = FindBestSolution(split_position, split_position[i][j] + 1, j);
  return "(" + left + right + ")";
}

改成递归版本：

int FindMinMatrixChainMultiplication(const vector<int>& matrix_dims,
                                     vector<vector<int>>* costs,
                                     vector<int>* split_position,
                                     int i, int j) {
  if (i >= j) return 0;
  if (costs[i][j] > 0) return costs[i][j];
  
  int min_cost = INT_MAX;
  for (int k = i; k <= j; ++k) {
    const auto cur_cost = matrix_dims[i-1]*matrix_dims[k]*matrix_dims[j] + 
      FindMinMatrixChainMultiplication(matrix_dims, costs, split_position, i, k) +
      FindMinMatrixChainMultiplication(matrix_dims, costs, split_position, k + 1, j); 
    if (cur_cost < min_cost) {
      min_cost = cur_cost;
      split_position[i][j] = k;
    }
  }
  costs[i][j] = min_cost;
  return min_cost;
}

optimal binary search tree

double ConstructOptimalBinarySearchTree(const vector<double>& nodes, const vector<double>& dummy,
                                        TreeNode*& root) {
  vector<vector<double>> costs(dummy.size()+1, vector<double>(dummy.size(), DBL_MAX));
  vector<vector<double>> w(dummy.size(), vector<double>(dummy.size(), 0.0));
  vector<vector<int>> roots(dummy.size(), vector<int>(dummy.size(), 0));
  
  for (int i = 1; i <= dummy.size(); ++i) {
    costs[i][i-1] = dummy[i-1];
    w[i][i-1] = dummy[i-1];
  }
  
  for (int len = 1; len <= nodes.size(); ++len) {
    for (int i = 1; i <= nodes.size() - len + 1; ++i) {
      int j = i + len - 1;
      w[i][j] = w[i][j-1] + nodes[j] + dummy[j];
      for (int r = i; r <= j; ++r) {
        const double cost = costs[i][r-1] + costs[r+1][j] + w[i][j];
        if (cost < costs[i][j]) {
          roots[i][j] = r;
          costs[i][j] = cost;
        }
      }
    } 
  }
  
  root = ConstructBinaryTree(roots, nodes, dummy, 1, nodes.size());
  
  return costs[1][nodes.size()];
}

// Dummy node not showing here.
TreeNode* ConstructBinaryTree(const vector<vector<int>>& roots, int stt_idx, int fin_idx) {
  if (stt_idx > fin_idx) return nullptr;
  TreeNode* root = new TreeNode(roots[stt_idx][fin_idx]);
  root->left = ConstructBinaryTree(roots, stt_idx, roots[stt_idx][fin_idx]-1);
  root->right = ConstrucBinaryTree(roots, roots[stt_idx][fin_idx]+1, fin_idx);
  return root;
}

Longest palindrome subsequence

string GetLongestPalindromeSubsequence(const string& str) {
  if (str.empty()) return "";
  vector<vector<bool>> record(str.size(), vector<bool>(str.size(), false));
  for (int i = 0; i < str.size(); ++i) record[i][i] = true;
  string res;
  for (int len = 2; len <= str.size(); ++len) {
    for (int i = 0; i < str.size() - len + 1; ++i) {
      if (record[i+1][i+len-2] && str[i][i+len-1]) {
        record[i][i+len-1] = true;
        res = str.substr(i, len);
      }
    }
  }
  return res;
}

neatly printing M(i) = min (M(k) + extra_line(k+1, i))

int FindMinNeatlyPrinting(const vector<int>& texts_len, const int M, vector<pair<int, int>>* solution) {
  if (M <= 0 || texts_len.empty()) return 0;
  
  vector<int> extra_cubes(texts_len.size(), INT_MAX);
  vector<int> trace(texts_len.size(), -1);
  vector<int> lens(texts_len.size()+1, 0);
  
  for (int i = 1; i <= texts_len.size(); ++i) lens[i] = lens[i-1] + texts_len[i];
  extra_cubes[0] = Pow3(lens[1]);
  
  for (int i = 0; i < texts_len; ++i) {
    for (int k = i - 1; k >= 0; --k) {
      const auto extra_space = GetExtraSpaces(k+1, i, lens, M);
      if (extra_cube >= 0) {
        const auto cur_cubes = extra_cubes[k] + (i == texts_len - 1?0:Pow3(extra_space));
        if (cur_cubes < extra_cubes[i]) {
          extra_cubes[i] = cur_cubes;
          trace[i] = k + 1;
        }
      } else break;
    }
  }
  
  FindSolution(trace, solution);
  return extra_cubes[texts_len.size()-1];
}

int Pow3(int base) {
  return base * base * base;
}

int GetExtraSpace(const int i, const int j, const vector<int>& lens, const int M) {
  return M - (lens[j+1] - lens[i+1] + j - i);
}

void FindSolution(const vector<int>& trace, vector<pair<int, int>>* solution) {
  for (int i = trace.size() - 1; i >= 0; i--) {
    *solution.push_back(make_pair(trace[i], i));
    i = trace[i];
  }  
}

break string：使用递归来计算（这里的计算$costs[i][j]$表示切点i到j的cost，当然另外一种状态表示方法可以把这个理解为块i到j的cost，区别是我写的这块比如i==j的时候，表示对第i个切点进行切分，$cost[i][j]$表示就是两段的长度。还有另外一个表示方法里面应该是$costs[i][i+2]$表示一样的意思，切点的位置在i+1）

int GetMinCostForStringBreaking(const vector<int>& L, const int n, const int i, const int j
                                vector<vector<int>>* costs) {
  if (i == j) return n;
  if (!n || i > j) return 0;
  
  if (costs[i][j] != INT_MAX) return costs[i][j];
  
  int cost = INT_MAX;
  
  for (int k = i; k <= j; ++k) {
    int new_cost = GetMinCostForStringBreaking(L, L[k] - L[i-1], i, k - 1, costs) + 
      GetMinCostForStringBreaking(L, L[j+1] - L[k], k+1, j, costs) + n;
    cost = min(cost, new_cost);
  }
  costs[i][j] = cost;
  return cost;
}

void CallGetMinCostForStringBreaking() {
  // L -> L[0] = 0; L[total_breaking + 1] = n
  // Call GetMinCostForStringBreaking(L, 1, total_breaking)
  // costs[1][total_breaking]
}

迭代的方式计算：

int GetMinCostForStringBreakking(const vector<int>& L, const int n) {
  vector<vector<int>> costs(L.size(), vector<int>(L.size(), 0));
  for (int len = 0; len <= L.size() - 2; ++len) {
    for (int i = 1; i <= L.size() - 2 - len; ++i) {
      const int j = i + len;
      int cost = INT_MAX;
      for (int k = i; k <= j; ++k) {
        int cur_cost = costs[i][k-1] + costs[k+1][j] + L[j+1] - L[i-1];
        cost = min(cost, cur_cost);
      }
      costs[i][j] = cost;
    }
  }
  return costs[1][L.size()-2];
}

使用另外一种写法表示状态：

int GetMinCostForStringBreaking(const vector<int>& L, const int n) {
  vector<int> new_L = L;
  new_L.insert(new_L.begin(), 0);
  new_L.push_back(n);
  vector<vector<int>> costs(L.size() + 2, vector<int>(L.size() + 2, 0));
  for (int len = 2; len < new_L.size(); ++len) {
    for (int i = 1; i <= new_L.size() - len; ++i) {
      const int j = i + len;
      int cost = INT_MAX;
      for (int k = i + 1; k < j; ++k) {
        int tmp_cost = costs[i][k] + costs[k][j] + new_L[j+1] - new_L[i-1];
        cost = min(tmp_cost, cost);
      }
      costs[i][j] = cost;
    }
  }
  return costs[1][L.size()];
}

两个序列

longest common subsequence

iterative method:

int LongestCommonSubsequence(const string& s1, const string& s2) {
  vector<vector<int>> record(s1.size() + 1, vector<int>(s2.size() + 1, 0));
  for (int i = 1; i <= s1.size(); ++i) {
    for (int j = 1; j < s2.size(); ++j) {
      record[i][j] = (s1[i-1] == s2[j-1])?record[i-1][j-1]+1:
           max(record[i-1][j], record[i][j-1]);
    }
  }
  return record[s1.size()][s2.size()];
}

给出最优解，使用额外的数组记录：

int MaxLongestCommonSubsequence(const string& s1, const string& s2, vector<int>* solution) {
  vector<vector<int>> record(s1.size()+1, vector<int>(s2.size()+1, 0));
  vector<vector<int>> trace(s1.size()+1, vector<int>(s2.size()+1, 0));
  for (int i = 1; i <= s1.size(); ++i) {
    for (int j = 1; j <= s2.size(); ++j) {
      if (s1[i-1] == s2[j-1]) {
        record[i][j] = record[i-1][j-1] + 1;
        trace[i][j] = 0;
      } else {
        if (record[i-1][j] > record[i][j-1]) {
          record[i][j] = record[i-1][j];
          trace[i][j] = -1;
        } else {
          record[i][j] = record[i][j-1];
          trace[i][j] = 1;
        }
      }
    }
  }
  
  FindBestSolution(trace, solution);
  
  return record[s1.size()][s2.size()];
}

void FindBestSolution(vector<vector<int>>& trace, vector<int>* solution) {
  int row = trace.size();
  int col = trace[0].size();
  while (row > 0 && col > 0) {
    if (!trace[row][col]) {
      *solution.push_back(row);
      --row;
      --col;
    } else {
      if (trace[row][col] == trace[row-1][col]) --row;
      else --col;
    }
  }
}

不使用额外的数组记录：

int FindLongestCommonSubsequence(const string& s1, const string& s2, vector<int>* solution) {
  vector<vector<int>> record(s1.size()+1, vector<int>(s2.size()+1, 0));
  for (int i = 1; i <= s1.size(); ++i) {
    for (int j = 1; j <= s2.size(); ++j) {
      record[i][j] = (s1[i-1] == s2[j-1]) ? record[i-1][j-1] + 1:
            max(record[i-1][j], record[i][j-1]);
    }
  }
  FindBestSolution(trace, solution);
}

void FindBestSolution(const vector<vector<int>>& trace, const string& s1, 
                      const string& s2,
                      vector<int>* solution) {
  int row = trace.size();
  int col = trace[0].size();
  while (row > 0 && col > 0) {
    if (trace[row][col] == trace[row-1][col-1] + 1 && s1[row] == s2[col]) {
      *solution.push_back(row);
      --row;
      --col;
    } else {
      if (trace[row][col] == trace[row-1][col]) --row;
      else --col;
    }
  }
}

很多时候是有多个相同长度的解的，找出所有的解：或者是有多少组最优解

int FindLongestCommonSubsequence(const string& s1, const string& s2, vector<vector<int>>* solutions) {
  vector<vector<int>> record(s1.size()+1, vector<int>(s2.size()+1, 0));
  for (int i = 1; i <= s1.size(); ++i) {
    for (int j = 1; j <= s2.size(); ++j) {
      record[i][j] = (s1[i-1] == s2[j-1]) ? record[i-1][j-1]+1 : 
                 max(record[i-1][j], [i][j-1]);
    }
  }
  FindBestSolution(s1, s2, trace, solutions, {}, s1.size(), s2.size());
  return record[s1.size()][s2.size()];
}

void FindBestSolution(const string& s1, const string& s2, const vector<vector<int>>& trace,
                      vector<vector<int>>* solutions, int row, int col)

对于空间进行优化：（O(mn) -> (2n) -> (n + 1)）空间优化对给出长度是可以的，但是需要给出具体的solution需要改进。

int FindLongestCommonSubsequence(const string& s1, const string& s2) {
  vector<int> record(s2.size()+1, 0);
  int lcs_pre = 0;
  for (int i = 1; i <= s1.size(); ++i) {
    for (int j = 1; j <= s2.size(); ++j) {
      int tmp = record[j];
      record[j] = s1[i-1] == s2[j-1] ? lcs_pre + 1 : 
            max(record[j], record[j-1]);
      lcs_pre = tmp;
    }
  }
  return record[s2.size()];
}

longest monotonically increasing subsequence: 这道问题可以先将vector排序再求LCS。

int FindLongestMonotonicallyIncreasingSubseuqnce(const vector<int>& nums, vector<int>* solution) {
  vector<int> record(nums.size()+1, 0);
  vector<int> trace(nums.size()+1, 0);
  for (int i = 1; i <= nums.size(); ++i) {
    for (int j = 1; j < i; ++j) {
      const auto flag = nums[j-1] >= nums[i-1];
      if (record[i] <= record[j]+flag) {
        record[i] = record[j] + flag;
        trace[i] = j;
      }
    }
  }
  FindBestSolution(nums, trace, record, solution);
  return *max_element(record.begin(), record.end());
}

void FindBestSolution(const vector<int>& nums, const vector<int>& trace, const vector<int>& record,
                      vector<int>* solution) {
  int idx = GetMaxLMIS(record);
  while (!idx) {
    *solution.push_back(nums[idx-1]);
    idx = trace[idx];
  }
}
  

图相关

longest simple path in a directed acyclic graph

int LongestSimplePath(const unordered_map<int, vector<int>>& paths, const map<pair<int, int>, int>& weight, 
                      const int stt_node, const int fin_node) {
  map<pair<int, int>, int> costs;
  queue<pair<int, int>> cur_nodes;
  cur_nodes.insert(stt_node)
}

image compression of RGB

int FindMinDiscuptPath(const vector<vector<int>>& A, const vector<vector<int>>& d, vector<int>* solution) {
  vector<vector<int>> record(A.size(), vector<int>(A[0].size()+2, INT_MAX));
  for (int i = 0; i < A[0].size(); ++i) {
    record[0][i+1] = A[0][i];
  }
  for (int i = 1; i < A.size(); ++i) {
    for (int j = 0; j < A[0].size(); ++j) {
      record[i][j+1] = d[i][j] + min(record[i-1][j], 
                       min(record[i-1][j+1], record[i-1][j+2]));
    }
  }
  FindSolution(record, distance(record[A.size()-1].begin(), *max_element(record[A.size()-1])), solution);
  return *max_element(record[A.size()-1]);
}

void FindSolution(const vector<vector<int>>& record, const int idx,
                  vector<int>* solution) {
  int cur_idx = idx;
  for (int i = record.size()-1; i >= 0; --i) {
    if (record[i][cur_idx] >= record[i][cur_idx-1] && record[i][cur_idx] >= record[i][cur_idx+1]) {
      *solution.push_back(cur_idx);
    } else if (record[i][cur_idx-1] >= record[i][cur_idx+1]) {
      *solution.push_back(cur_idx-1);
      --cur_idx;
    } else {
      *solution.push_back(cur_idx+1);
      ++cur_idx;
    }
  }
}

planning an investment strategy

int FindBestInvestmentStrategy(const vector<vector<int>>& r, const int m, vector<int>* solution, 
                               const double d, const double f1, const double f2) {
  const int n = r[0].size();
  vector<vector<int>> trace(n, vector<int>(m, 0));
  vector<double> prev_record = r[0];
  vector<double> cur_record(n, DBL_MIN);
  
  for (int i = 1; i < m; ++i) {
    for (int j = 0; j < n; ++j) {
      double cur_r = prev_record[j] + f1;
      trace[i][j] = j;
      for (int k = 0; k < n; ++k) {
        if (prev_record[k] + f2 > cur_r) {
          cur_r = prev_record[k] + f2;
          trace[i][j] = k;
        }
      }
      cur_record[j] = cur_r;
    }
    swap(prev_record, cur_record);
  }
  int fin_idx = distance(prev_record.begin(), *max_element(prev_record.begin(), prev_record.end()));
  
  *solution.push_back(fin_idx);
  for (int i = m - 1; i >= 1; --i) {
    *solution.push_back(trace[i][fin_idx]);
    fin_idx = *solution.back();
  }
  
  return prev_record[fin_idx];
}

inventory planning

int FindInventoryPlanningStrategy(const vector<int>& demands, const int m, const int n, const int c, const vector<int>& h,
                                  vector<int>* hiring_plan) {
  vector<int> acc_demands = demands;
  acc_demands.insert(0, acc_demands.begin());
  for (int idx = 2; idx <= acc_demands.size(); ++idx) acc_demands[idx] += acc_demands[idx-1];
  vector<vector<int>> costs(n + 1, vector<int>(acc_demands.back(), INT_MAX));
  // Store the previous choosing machines.
  vector<vector<int>> trace(n + 1, vector<int>(acc_demands.back(), 0));
  
  for (int i = 1; i <= n; ++i) {
    const auto& prec_cost = costs[i-1];
    for (int j = acc_demands[i]; j <= acc_demands.back(); ++j) {
      for (int k = acc_demands[i-1]; k <= acc_demands.back(); ++k) {
        const int cur_cost = costs[i-1][k] + (j - k <= m?0:c*(j - k - m)) + h[k - acc_demands[i-1]];
        if (costs[i][j] < cur_cost) {
          costs[i][j] = cur_cost;
          trace[i][j] = k;
        }
      }
    }
  }
  *hiring_plan.push_back(acc_demands.back());
  GetSolution(trace, hiring_plan);
  return costs[n][acc_demands.back()];
}

void GetSolution(const vector<vector<int>>& trace, vector<int>* solution) {
  int cur_demand = trace[0].size();
  for (int idx = n; idx >= 1; --idx) {
    cur_demand = trace[idx][cur_demand];
    *solution.push_back(cur_demand);
  }
}

Viterbi for speech recognition

// Find a path of target sequence
vector<int> FindPath(const unordered_map<int, vector<int>> &edges, const map<pair<int, int>, int> &weight, 
                     const vector<int> &sequence, 
                     const int idx, const int vertex) {
  if (idx == sequence.size()) return {};
  
  for (const auto &ele : edges.at(vertex).second) {
    if (weight.at(make_pair(vertex, ele)) == sequence[idx]) {
      vector<int> res = FindPath(edges, weight, sequence, idx + 1, ele);
      if (sequence.size() - res.size() == idx + 1) {
        res.push_back(vertex);
        return res;
      }
    }
  }
  return {};
}

// Find the highest probability 
double FindPath(const unordered_map<int, vector<int>> &edges, const map<pair<int, int>, int> &sigma,
             const map<pair<int, int>, double> &probability, const vector<int> &sequence,
             const int idx, const int cur_vertex, map<pair<int, int>, pair<int, double>>* traces) {
  const auto k = make_pair(idx, cur_vertex);
  if (idx == sequence.size()) {
    traces[make_pair(idx, cur_vertex)] = make_pair(-1, 0);
    return 0;
  }
  
  if (traces.find(k) != traces.end()) return traces[k].second;
  
  int prob = INT_MIN;
  for (const auto& v : edges[vertex].second) {
    const auto next_prob = FindPath(edges, sigma, probability, sequence, idx + 1, v, traces);
    if (next_prob == INT_MIN) continue;
    const auto cur_prob = next_prob + probability[make_pair(vertex, v)];
    if (cur_prob > prob) {
      traces[make_pair(idx, vertex)] = make_pair(v, cur_prob);
      prob = cur_prob;
    }
  }
  return prob;
}

void FindBestSolutionFromTrace(const map<pair<int, int>, pair<int, double>> &traces,
                               const int v0, vector<int>* solution) {
  auto cur_node = traces.at(make_pair(0, v0));
  *solution.push_back(v0);
  int idx = 1;
  while (cur_node.second.first >= 0) {
    cur_node = trace.at(make_pair(idx, cur_node.first));
    *solution.push_back(cur_node.first);
    ++idx;
  }
}

planning a company party

// 1. the tree could be used as unordered_map<int, vector<int>>  supervisor -> emplyees
// unordered_map<int, double> rank of the conviviality
// 2. use the tree structure directly
struct Employee {
  double rank;
  double children_sum = 0.0;
  bool choice = false;  // choose current node or not.
  vector<Employee*> children;
};

double FindCompanyPartyList(Employee* root) {
  if (!root) return 0;
  
  double children_sum = 0.0;
  double cc_sum = 0.0;
  for (const auto p : root->children) {
    double cur_rank = FindCompanyPartyList(p);
    children_sum += max(cur_rank, p->children_sum);
    cc_sum += p->children_sum;
  }
  root->children_sum = max(cc_sum + root->rank, children_sum);
  if (cc_sum + root->rank > children_sum) {
    root->choice = true;
  } else {
    root->choice = false;
  }
  return max(cc_sum + root->rank, children_sum);
}

void GetCompanyPartyList(Employee *root, vector<Employee*> *solution) {
  if (!root) return;
  if (root->choice) *solution.push_back(root);
  for (const auto p : root->children) {
    if (p->choice) *solution_push_back(p);
    GetCompanyPartyList(p, solution);
  }
}

Knapsack

vector<int> FindMaximumVORPFreeAgents(const int X, const vector<vector<int>> &costs, const vector<vector<double>> &vorp, double* max_vorp) {
  int N = costs.size();
  if (!N) return {};
  
  int P = costs[0].size();
  assert(costs.size() == vorp.size() && P > 0 && P == vorp[0].size());
  
  vector<vector<double>> selected_vorps(N+1, vector<double>(X+1, 0));
  vector<vector<int>> selected_players(N+1, vector<int>(X+1, 0));
  for (int i = 1; i <= N; ++i) {
    for (int j = 1; j <= X; ++j) {
      selected_vorps[i][j] = selected_vorps[i-1][j];
      for (int k = 1; k <= P; ++k) {
        if (j - costs[i][k] >= 0) {
          if (selected_vorps[i][j] < selected_vorps[i-1][j-costs[i][k] + vorp[i][k]]) {
            selected_vorps[i][j] = selected_vorps[i-1][j-costs[i][k] + vorp[i][k]];
            selected_players[i][j] = k;
          }
        }
      }
    }
  }
  *max_vorp = selected_vorps[N][X];
  vector<int> choose_players;
  int cur_X = X;
  for (int i = N; i >= 1; --i) {
    int k = selected_players[i][cur_X];
    choose_players.push_back(k);
    cur_X -= costs[i][k];
  }
  return choose_players;
}

Reference from: csdn

动态规划的元素

什么时候可以使用动规？在有最优子结构(optimal substructrue)和重叠子问题(overlapping subproblems)的时候。最优子结构就是解决优化问题的时候使用的子问题的解，也是该子问题的最优解。问题的最优解可以通过组合子问题的最优解得到，这里用到了一个思想“cut and paste”。动规的整个思想更加贴近于归纳推理(inductive reasoning)。

动规的运行时间依赖于子问题的数量以及每个子问题的选择。有些问题里面不存在最优子结构，比如有向最长路径，需要子问题之间没有依赖性。重叠子问题，求解问题中需要使用大量重叠子问题的解，使用动态规划记忆化搜索就更有价值。

merge sort 无法使用dp的原因是因为它没有最优子结构，子问题之间没有overlap。

No One

DP

定义

单个序列

两个序列

图相关

Knapsack

动态规划的元素

Current to 91

DP

定义

单个序列

两个序列

图相关

Tree related

Knapsack

动态规划的元素

Current to 91