673. 最长递增子序列的个数

673. 最长递增子序列的个数

dp+记方案数

这应该是个记方案数的经典题，还有就是dijkstra记录方案数

class Solution {
 public:
  int findNumberOfLIS(vector<int>& nums) {
    int n = nums.size();
    int f[n], cnt[n];
    memset(f, 0, sizeof f), memset(cnt, 0, sizeof cnt);
    int mx = 0, res = 0;
    for (int i = 0; i < n; i++) {
      f[i] = 1, cnt[i] = 1;
      for (int j = 0; j < i; j++) {
        if (nums[j] < nums[i]) {
          if (f[i] < f[j] + 1) {
            f[i] = f[j] + 1;
            cnt[i] = cnt[j];
          } else if (f[i] == f[j] + 1) {
            cnt[i] += cnt[j];
          }
        }
      }
      if (mx < f[i]) {
        mx = f[i];
        res = cnt[i];
      } else if (mx == f[i]) {
        res += cnt[i];
      }
    }
    return res;
  }
};