Easy C++ DP with one dimension vector only and explanation


  • 1
    class Solution {
    public:
      int maxA(int N) {
        if (N <= 3)
          return N;
    
        vector<int> f(N + 1);
        for (int i = 1; i <= 3; i++)
          f[i] = i;
    
        for (int i = 4; i <= N; i++) {
          int max = i;
          for (int j = 3; j <= i - 1; j++) {
            //First output j - 1 "A"s, then copy and paste it i - j - 1 times, so
            //totally you get f[i - j - 1 + 1] * (j - 1) "A"s.
            int m = f[i - j] * (j - 1); 
            if (m > max)
              max = m;
          }
          f[i] = max;
        }
    
        return f[N];
      }
    };
    
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.