664. Strange Printer | Dynamic Programming | Leetcode POTD Explained

แชร์
ฝัง
  • เผยแพร่เมื่อ 27 พ.ย. 2024

ความคิดเห็น • 11

  • @codeby_naruto
    @codeby_naruto  3 หลายเดือนก่อน +1

    Code :-
    class Solution {
    public:
    vector dp; // DP table to store results of subproblems
    // Recursive function to solve the problem for substring s[i...j]
    int solve(string &s, int i, int j) {
    // Base case: If the substring is of length 1, only 1 turn is needed
    if (i == j) return 1;
    // Return the stored result if it has been computed before
    if (dp[i][j] != -1) return dp[i][j];
    int minTurn = INT_MAX; // Initialize minimum turns to a large value
    // Try every possible partition point k in the substring
    for (int k = i; k < j; k++) {
    // Calculate the minimum turns for the left and right parts of the partition
    int LeftPart = solve(s, i, k);
    int RightPart = solve(s, k + 1, j);
    // Update the minimum turns needed considering this partition
    minTurn = min(minTurn, LeftPart + RightPart);
    }
    // If characters at the start and end of the substring are the same, reduce the count by 1
    return dp[i][j] = (s[i] == s[j]) ? minTurn - 1 : minTurn;
    }
    // Main function to calculate the minimum number of turns needed for the entire string
    int strangePrinter(string s) {
    int n = s.size();
    // Initialize the DP table with -1, indicating that no subproblem has been solved yet
    dp.resize(n + 1, vector(n + 1, -1));
    // Compute the result for the entire string from index 0 to n-1
    return solve(s, 0, n - 1);
    }
    };

  • @yashyadav824
    @yashyadav824 3 หลายเดือนก่อน +3

    Very Well Explained Bro👍

    • @codeby_naruto
      @codeby_naruto  3 หลายเดือนก่อน

      Thank you ❤️

  • @sainathpatil2674
    @sainathpatil2674 3 หลายเดือนก่อน +1

    Good explanation

    • @codeby_naruto
      @codeby_naruto  3 หลายเดือนก่อน

      Thank you ❤️❤️

  • @shubhamjaiswal7645
    @shubhamjaiswal7645 3 หลายเดือนก่อน +1

    nice one

    • @codeby_naruto
      @codeby_naruto  3 หลายเดือนก่อน

      Thank you ❤️

  • @a3rdtierguy864
    @a3rdtierguy864 3 หลายเดือนก่อน +1

    Bhaiya ye pahle aapne 10^8 karke kaise complexity bataya next problem jab karana to please acche se samjhana bhaiya

    • @codeby_naruto
      @codeby_naruto  3 หลายเดือนก่อน +1

      Ok sure, I'll make sure to explain it clearly next time.
      Thanks for the feedback! ✨❤️

  • @sagarmondal8082
    @sagarmondal8082 3 หลายเดือนก่อน

    TLE

    • @codeby_naruto
      @codeby_naruto  3 หลายเดือนก่อน +1

      it's Accepted ✨ Check again ...