Dynamic Programming

int f(int X) { // f(X)=最少用多少枚硬币拼出X
  if (X == 0) { // 0元钱只要0枚硬币
    return 0;
  }
  int result = 0x3f3f3f3f; // INT_MAX; // 初始化用无穷大
  if (X >= 2) { // 最后一枚硬币是2元
    result = std::max(f(X - 2) + 1, result);
  }
  if (X >= 5) { // 最后一枚硬币是5元
    result = std::max(f(X - 5) + 1, result);
  }
  if (X >= 7) { // 最后一枚硬币是7元
    result = std::max(f(X - 7) + 1, result);
  }
  return result;
}

class Solution {
 public:
                        // coins       // amount
                        // {2, 5, 7}   // 27
  int coinChange(std::vector<int>& A, int M) {
    // 0....n: [n+1]
    // 0...n-1: [n]
    std::vector<int> f(M + 1);
    int n = A.size(); // number of kinds of coins

    // initialization
    f[0] = 0;

    int i, j;
    // f[1], f[2], ..., f[27]
    for (i = 1; i <= M; ++i) {
      f[i] = INT_MAX;
      // last coin A[j]
      // f[i] = min{f[i - A[0]] + 1, ..., f[i - A[n - 1]] + 1}
      for (j = 0; j < n; ++j) {
        if (i >= A[j] && f[i - A[j]] != INT_MAX) {
          f[i] = std::min(f[i - A[j]] + 1, f[i]);
        }
      }
    }

    if (f[M] == INT_MAX) {
      f[M] = -1;
    }

    return f[M];
  }
};

class Solution {
 public:
  int uniquePaths(int m, int n) {
    std::vector<std::vector<int>> f(m, std::vector<int>(n));
    int i, j;
    for (i = 0; i < m; ++i) { // row: top to bottom
      for (j = 0; j < n; ++j) { // column: left to right
        if (i == 0 || j == 0) {
          f[i][j] = 1;
        } else {
          f[i][j] = f[i - 1][j] + f[i][j - 1];
        }
      }
    }
    return f[m - 1][n - 1];
  }
};

class Solution {
 public:
  bool canJump(std::vector<int>& A) {
    int n = A.size();
    std::vector<bool> f(n);
    f[0] = true; // initialization

    for (int j = 1; j < n; ++j) {
      f[j] = false;
      // previous stone i
      // last jump is from i to j
      for (int i = 0; i < j; ++i) {
        if (f[i] && i + A[i] >= j) {
          f[j] = true;
          break;
        }
      }
    }

    return f[n - 1];
  }
};

class Solution {
 public:
  int uniquePathsWithObstacles(std::vector<std::vector<int>>& A) {
    if (A.size() == 0 || A[0].size() == 0) {
      return 0;
    }

    int m = A.size();
    int n = A[0].size();
    std::vector<std::vector<int>> f(m, std::vector<int>(n));
    int i, j;
    for (i = 0; i < m; ++i) {
      for (j = 0; j < n; ++j) {
        if (A[i][j] == 1) {
          //obstacle
          f[i][j] = 0;
          continue;
        }

        if (i == 0 && j == 0) {
          f[i][j] = 1;
          continue;
        }

        f[i][j] = 0;
        // if it is not on 0-th row
        if (i > 0) {
          f[i][j] += f[i - 1][j];
        }

        // if it is not on 0-th column
        if (j > 0) {
          f[i][j] += f[i][j - 1];
        }
      }
    }

    return f[m - 1][n - 1];
  }
};

// Version 1
class Solution {
 public:
  int minCost(std::vector<std::vector<int>>& costs) {
    int n = costs.size();
    if (n == 0) {
      return 0;
    }

    std::vector<std::vector<int>> f(n + 1, std::vector<int>(3)); // seq-type
    f[0][0] = f[0][1] = f[0][2] = 0; // initialization
    // first i houses 前i栋
    for (int i = 1; i <= n; ++i) {

      // house i - 1's color is j
      for (int j = 0; j < 3; ++j) {
        f[i][j] = 0x3f3f3f3f;

        // house i - 2's color is k
        for (int k = 0; k < 3; ++k) {
          if (j == k) {
            continue;
          }

          f[i][j] = std::min(f[i][j], f[i - 1][k] + costs[i - 1][j]);
        }
      }
    }

    return std::min(f[n][0], std::min(f[n][1], f[n][2]));
  }
};

// Version 2
class Solution {
 public:
  int minCost(std::vector<std::vector<int>>& costs) {
    int n = costs.size();
    if (n == 0) {
      return 0;
    }

    std::vector<std::vector<int>> f(n + 1, std::vector<int>(3)); // seq-type
    f[0][0] = f[0][1] = f[0][2] = 0; // initialization
    // first i houses
    for (int i = 1; i <= n; ++i) {
        f[i][0] = std::min(f[i - 1][1] + costs[i - 1][0], f[i - 1][2] + costs[i - 1][0]);
        f[i][1] = std::min(f[i - 1][0] + costs[i - 1][1], f[i - 1][2] + costs[i - 1][1]);
        f[i][2] = std::min(f[i - 1][0] + costs[i - 1][2], f[i - 1][1] + costs[i - 1][2]);
    }

    return std::min(f[n][0], std::min(f[n][1], f[n][2]));
  }
};

class Solution {
 public:
  int numDecodings(std::string& s) {
    int n = s.size();
    if (n == 0) {
      return 0;
    }
    std::vector<int> f(n + 1, 0);
    int i;
    f[0] = 1; // initialization; 当物理意义不明确的时候，推断当前的初始化是否能得到正确的结果
    // first i digits: s[0], ..., s[i - 1]
    for (i = 1; i <= n; ++i) {
      f[i] = 0;
      // last one digit --> letter
      // s[i - 1] == [1, 9]
      if (s[i - 1] != '0') {
        f[i] += f[i - 1];
      }

      // last two digits --> letter
      // s[i - 2]s[i - 1] == [10, 26]
      if (i >= 2 && (s[i - 2] == '1' || (s[i - 2] == '2' && s[i - 1] <= '6'))) {
        f[i] += f[i - 2];
      }
    }

    return f[n];
  }
};

// Mine correct version
class Solution {
 public:
  int minPathSum(std::vector<std::vector<int>>& grid) {
    int n = grid.size();
    int m = grid[0].size();
    if (n == 0 || m == 0) {
      return 0;
    }

    std::vector<std::vector<int>> f(n, std::vector<int>(m));
    f[0][0] = grid[0][0];
    for (int i = 1; i < m; ++i) {
      f[0][i] = f[0][i - 1] + grid[0][i];
    }

    for (int i = 1; i < n; ++i) {
      f[i][0] = f[i - 1][0] + grid[i][0];
    }

    for (int i = 1; i < n; ++i) {
      for (int j = 1; j < m; ++j) {
        f[i][j] = std::min(f[i - 1][j], f[i][j - 1]) + grid[i][j];
      }
    }

    return f[n - 1][m - 1];
  }
};

// Official correct version
class Solution {
 public:
  int minPathSum(std::vector<std::vector<int>>& grid) {
    int n = grid.size();
    int m = grid[0].size();
    if (n == 0 || m == 0) {
      return 0;
    }

    std::vector<std::vector<int>> f(n, std::vector<int>(m));
    for (int i = 0; i < n; ++i) {
      for (int j = 0; j < m; ++j) {
        if (i == 0 && j == 0) {
          f[i][j] = grid[i][j];
          continue;
        }
        f[i][j] = INT_MAX;
        // if it has a grid above
        if (i > 0) {
          f[i][j] = std::min(f[i][j], f[i - 1][j] + grid[i][j]);
        }

        // if it has a grid to the left
        if (j > 0) {
          f[i][j] = std::min(f[i][j], f[i][j - 1] + grid[i][j]);
        }
      }
    }

    return f[n - 1][m - 1];
  }
};

class Solution {
 public:
  int minPathSum(std::vector<std::vector<int>>& grid) {
    int n = grid.size();
    int m = grid[0].size();
    if (n == 0 || m == 0) {
      return 0;
    }

    std::vector<std::vector<int>> f(n, std::vector<int>(m));
    std::vector<std::vector<int>> pi(n, std::vector<int>(m));
    // if f[i][j] depends on f[i - 1][j], pi[i][j] = 0
    // if f[i][j] depends on f[i][j - 1], pi[i][j] = 1

    for (int i = 0; i < n; ++i) {
      for (int j = 0; j < m; ++j) {
        if (i == 0 && j == 0) {
          f[i][j] = grid[i][j];
          continue;
        }

        f[i][j] = INT_MAX;
        // if it has a grid above
        if (i > 0) {
          f[i][j] = std::min(f[i][j], f[i - 1][j] + grid[i][j]);
          if (f[i][j] == f[i - 1][j] + grid[i][j]) {
            pi[i][j] = 0;
          }
        }

        // if it has a grid to the left
        if (j > 0) {
          f[i][j] = std::min(f[i][j], f[i][j - 1] + grid[i][j]);
          if (f[i][j] == f[i][j - 1] + grid[i][j]) {
            pi[i][j] = 1;
          }
        }
      }
    }

    // (n - 1, m - 1)
    std::vector<std::vector<int>> path(n + m - 1, std::vector<int>(2));
    int p;
    int i = n - 1;
    int j = m - 1;
    // infer the path backward from (n - 1, m - 1)
    for (p = n + m - 2; p >= 0; --p) {
      path[p][0] = i;
      path[p][1] = j;
      if (p == 0) {
        break;
      }
      if (pi[i][j] == 0) {
        --i;
      } else {
        --j;
      }
    }

    for (p = 0; p < n + m - 1; ++p) {
      std::cout << "(" << path[p][0] << ", " << path[p][1] << "): " << grid[path[p][0]][path[p][1]] << std::endl;
    }

    return f[n - 1][m - 1];
  }
};

# expected result from the test case: [[1,5,7,6,8],[4,7,4,4,9],[10,3,2,3,2]]
(0, 0): 1
(1, 0): 4
(1, 1): 7
(2, 1): 3
(2, 2): 2
(2, 3): 3
(2, 4): 2

class Solution {
 public:
  int minPathSum(std::vector<std::vector<int>>& grid) {
    int n = grid.size();
    int m = grid[0].size();
    if (n == 0 || m == 0) {
      return 0;
    }

    std::vector<std::vector<int>> f(2, std::vector<int>(m));

    int old, now = 0;
    // old: f[old][...] is holding f[i - 1][...]
    // now: f[now][...] is holding f[i][...]

    for (int i = 0; i < n; ++i) {
      // swap old and now
      old = now;
      now = 1 - now; // 0-->1, 1-->0

      // 将所有的 f[i] 变成 f[now]； f[i - 1] 变成 f[old]
      for (int j = 0; j < m; ++j) {
        if (i == 0 && j == 0) {
          f[now][j] = grid[i][j];
          continue;
        }
        f[now][j] = INT_MAX;
        // if it has a grid above
        if (i > 0) {
          f[now][j] = std::min(f[now][j], f[old][j] + grid[i][j]);
        }

        // if it has a grid to the left
        if (j > 0) {
          f[now][j] = std::min(f[now][j], f[now][j - 1] + grid[i][j]);
        }
      }
    }

    return f[now][m - 1];
  }
};

class Solution {
 public:
  int maxKilledEnemies(std::vector<std::vector<char>>& grid) {
    if (grid.size() == 0 || grid[0].size() == 0) {
      return 0;
    }

    int n = grid.size();
    int m = grid[0].size();

    std::vector<std::vector<int>> up(n, std::vector<int>(m));
    std::vector<std::vector<int>> down(n, std::vector<int>(m));
    std::vector<std::vector<int>> left(n, std::vector<int>(m));
    std::vector<std::vector<int>> right(n, std::vector<int>(m));

    // up
    // count E like prefix_sum
    // encounter W start from 0
    for (int i = 0; i < n; ++i) {
      for (int j = 0; j < m; ++j) {
        up[i][j] = 0;
        if (grid[i][j] != 'W') {
          if (grid[i][j] == 'E') {
            ++up[i][j];
          }

          if (i > 0) {
            up[i][j] += up[i - 1][j];
          }
        }
      }
    }

    // down 
    for (int i = n - 1; i >= 0; --i) {
      for (int j = 0; j < m; ++j) {
        down[i][j] = 0;
        if (grid[i][j] != 'W') {
          if (grid[i][j] == 'E') {
            ++down[i][j];
          }

          if (i < n - 1) {
            down[i][j] += down[i + 1][j];
          }
        }
      }
    }

    // left
    for (int i = 0; i < n; ++i) {
      for (int j = 0; j < m; ++j) {
        left[i][j] = 0;
        if (grid[i][j] != 'W') {
          if (grid[i][j] == 'E') {
            ++left[i][j];
          }

          if (j > 0) {
            left[i][j] += left[i][j - 1];
          }
        }
      }
    }

    // right
    for (int i = 0; i < n; ++i) {
      for (int j = m - 1; j >= 0; --j) {
        right[i][j] = 0;
        if (grid[i][j] != 'W') {
          if (grid[i][j] == 'E') {
            ++right[i][j];
          }

          if (j < m - 1) {
            right[i][j] += right[i][j + 1];
          }
        }
      }
    }

    int result = 0;
    for (int i = 0; i < n; ++i) {
      for (int j = 0; j < m; ++j) {
        if (grid[i][j] == '0') { // empty
          result = std::max(result, up[i][j] + down[i][j] + left[i][j] + right[i][j]);
        }
      }
    }

    return result;
  }
};

class Solution {
 public:
  std::vector<int> countBits(int num) {
    std::vector<int> f(num + 1);
    f[0] = 0;
    for (int i = 1; i <= num; ++i) {
      f[i] = f[i >> 1] + (i % 2);
    }

    return f;
  }
};

class Solution {
 public:
  int lengthOfLIS(std::vector<int>& nums) {
    if (nums.size() == 0) {
      return 0;
    }
    std::vector<int> f(nums.size(), 1);
    for (int i = 1; i < nums.size(); ++i) {
      // compare current number with all previous numbers
      // if satisfies the increasing condition then compete
      // [0, i)
      for (int j = 0; j < i; ++j) {
        if (nums[i] > nums[j]) {
          f[i] = std::max(f[i], f[j] + 1);
        }
      }
    }
    return *max_element(f.begin(), f.end());
  }
};

class Solution {
 public:
  int rob(std::vector<int>& A) {
    int n = A.size();
    if (n == 0) {
      return 0;
    }
    std::vector<std::vector<int>> dp(n, std::vector<int>(2, 0));

    dp[0][0] = 0;
    dp[0][1] = A[0];

    for (int i = 1; i < n; ++i) {
      // 如果不抢第i个，取前i - 1个位置dp较大值
      dp[i][0] = std::max(dp[i - 1][0], dp[i - 1][1]);
      // 如果抢第i个，前一个不抢，考虑从前i - 2个位置的dp值转移，即i - 1选择不打劫
      dp[i][1] = A[i] + dp[i - 1][0];
    }

    int result = std::max(dp[n - 1][0], dp[n - 1][1]);
    return result;
  }
};

$$\begin{align}
dp[i] &= 前`i`个数取出的最大和(不关心第`i`个取或者不取) \\ 
      &= max(dp[i - 2] + a[i], dp[i - 1]) 以此来避免取相邻的两个房子 \\
优化：dp[i \% 3] &= 前`i`个数取出的最大和(不关心第`i`个取或者不取) \\ 
      &= max(dp[(i - 2) \% 3] + a[i], dp[(i - 1) \% 3]) 以此来避免取相邻的两个房子 
\end{align}$$

class Solution {
 public:
  int maximalRectangle(std::vector<std::vector<char>>& matrix) {
    if (matrix.size() == 0 || matrix[0].size() == 0) {
      return 0;
    }

    int ans = 0;
    int n = matrix.size();
    int m = matrix[0].size();
    std::vector<std::vector<int>> dp(n, std::vector<int>(m + 1));
    for (int i = 0; i < n; ++i) { // 每个位置上方有多少连续的1
      for (int j = 0; j < m; ++j) {
        if (i == 0 && matrix[i][j] == '1') {
          dp[i][j] = 1;
          continue;
        }
        if (matrix[i][j] == '1') {
          dp[i][j] = dp[i - 1][j] + 1;
        }
      }
    }

    for (int i = 0; i < n; ++i) { // 把每一行作为底找最大矩形
      ans = std::max(ans, largestRectangleArea(dp[i]));
    }
    return ans;
  }

 private:
  int largestRectangleArea(std::vector<int>& heights) {
    std::deque<int> S;
    heights[heights.size() - 1] = 0;
    int sum = 0;
    for (int i = 0; i < heights.size(); ++i) {
      if (S.empty() || heights[i] > heights[S.back()]) {
        S.push_back(i);
      } else {
        int temp = S.back();
        S.pop_back();
        sum = std::max(sum, heights[temp] * (S.empty() ? i : i - S.back() - 1));
        --i; // 拿着右边界，寻找左边界
      }
    }
    return sum;
  }
};

// LHC version: Monotonic-stack answer
class Solution {
 public:
  int largestRectangleArea(std::vector<int>& height) {
    std::deque<int> S;

    std::vector<int> heights = height;
    heights.push_back(-1);

    int sum = 0;
    for (int i = 0; i < heights.size(); ++i) {
      if (S.empty() || heights[i] > heights[S.back()]) {
        S.push_back(i);
      } else {
        int temp = S.back();
        S.pop_back();
        sum = std::max(sum, heights[temp] * (S.empty() ? i : i - S.back() - 1));
        --i; // 拿着右边界，寻找左边界
      }
    }
    return sum;
  }
};

// Correct Monotonic-stack answer from other students
class Solution {
 public:
  int largestRectangleArea(std::vector<int>& heights) {
    if (heights.size() == 0) {
      return 0;
    }

    std::deque<int> stack;
    int sum = 0;
    for (int i = 0; i <= heights.size(); ++i) {
      int curt = (i == heights.size()) ? -1 : heights[i];
      while (!stack.empty() && curt <= heights[stack.back()]) {
        int h = heights[stack.back()];
        stack.pop_back();
        int w = stack.empty() ? i : i - stack.back() - 1;
        sum = std::max(sum, h * w);
      }
      stack.push_back(i);
    }

    return sum;
  }
};