C++ DP solution


  • 0
    H
    class Solution {
    public:
        int magicalString(int n) {
            if (n < 2) return n;
            vector<int> dp(n+1);
            dp[1] = 1;
            dp[2] = 2;
            int res = 1;
            int end = 1;
            int j = 0;
            for (int i = 3; i <= n; i++) {
                if (end < i) end += dp[++j+1];
                dp[i] = j % 2 + 1;
                if (j % 2 == 0) res++;
            }
            return res;
        }
    };
    

  • 0
    L

    Can you explain it? what's in 'dp'?


Log in to reply
 

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