Java Technologies Dynamic Programming এর মাধ্যমে Grid Problem সমাধান গাইড ও নোট

Dynamic Programming (DP) একটি শক্তিশালী কৌশল যা সমস্যা সমাধানের জন্য overlapping subproblems এবং optimal substructure ব্যবহার করে। এটি সাধারণত সমস্যাগুলির পুনরাবৃত্তি সাব-সমস্যাগুলির সমাধান করার জন্য ব্যবহৃত হয় এবং অতিরিক্ত কাজ পুনরাবৃত্তি করতে এড়াতে সাহায্য করে।

এই গাইডে, আমরা Grid Problem সমাধান করার জন্য Dynamic Programming পদ্ধতি ব্যবহার করব। গ্রিড সমস্যা সাধারণত 2D অ্যারে বা ম্যাট্রিক্স ব্যবহার করে বিভিন্ন রকমের পথ, রুটিন বা সেল ভিজিট করতে হয়, এবং DP সেখানেও কার্যকরী হতে পারে।

1. Grid Problem: Minimum Path Sum

ধরা যাক, আমাদের একটি m x n গ্রিড (ম্যাট্রিক্স) দেওয়া হয়েছে, যেখানে প্রতিটি সেলে কিছু সংখ্যার মান রয়েছে। আমাদের লক্ষ্য হলো, grid's top-left (0,0) থেকে bottom-right (m-1, n-1) কোঅর্ডিনেটে পৌঁছানো, এমনভাবে যে, আমরা যতটা সম্ভব ছোট পাথের সমষ্টি পাবো।

1.1. Problem Definition

• একটি 2D grid দেওয়া হয়েছে, যেখানে প্রতিটি সেলে একটি সংখ্যা রয়েছে।
• আপনি top-left থেকে bottom-right কোঅর্ডিনেটে পৌঁছাতে চাইছেন, কিন্তু প্রতিটি সেল পাস করার জন্য একটি পাথের সমষ্টি যোগ করতে হবে।
• আপনি শুধুমাত্র down এবং right দিকে চলতে পারবেন।

1.2. Dynamic Programming Approach

এটি একটি minimum path sum সমস্যা। Dynamic Programming এর মাধ্যমে, আমরা top-down বা bottom-up পদ্ধতিতে কাজ করতে পারি। এখানে, আমরা bottom-up পদ্ধতিতে সমাধান দেখবো।

1. Subproblem: কোন সেলে পৌঁছানোর জন্য, আমরা minimum path sum জানি, সেক্ষেত্রে সেই সেলে পৌঁছানোর জন্য যে সেরা পথটি হবে, তা নির্ধারণ করা হবে।
2. Recursive Formula: একটি সেল (i, j) এর জন্য, তার জন্য minimum path sum হবে: $$dp[i][j] = grid[i][j] + \min(dp[i+1][j], dp[i][j+1])$$ যেখানে dp[i][j] হলো (i, j) সেলে পৌঁছানোর সর্বনিম্ন পাথের সমষ্টি।

1.3. Java Code Implementation

public class GridProblem {

    // Function to find the minimum path sum
    public int minPathSum(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;

        // Create a 2D DP array
        int[][] dp = new int[m][n];

        // Initialize the starting point
        dp[0][0] = grid[0][0];

        // Fill the first row (can only come from left)
        for (int i = 1; i < n; i++) {
            dp[0][i] = dp[0][i - 1] + grid[0][i];
        }

        // Fill the first column (can only come from above)
        for (int i = 1; i < m; i++) {
            dp[i][0] = dp[i - 1][0] + grid[i][0];
        }

        // Fill the rest of the grid (can come from left or top)
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = grid[i][j] + Math.min(dp[i - 1][j], dp[i][j - 1]);
            }
        }

        // The result is in the bottom-right cell
        return dp[m - 1][n - 1];
    }

    public static void main(String[] args) {
        GridProblem problem = new GridProblem();

        // Example grid
        int[][] grid = {
            {1, 3, 1},
            {1, 5, 1},
            {4, 2, 1}
        };

        System.out.println("Minimum Path Sum: " + problem.minPathSum(grid));  // Output: 7
    }
}

1.4. Explanation:

1. dp[0][0]: প্রথম সেলের মানটি সরাসরি grid[0][0] থেকে নেওয়া হয়।
2. First Row: প্রথম সারির জন্য, কেবলমাত্র বাম পাশ থেকে আসা সম্ভব, তাই প্রতিটি সেলের মান আগের সেলের মান যোগ করে পাওয়া যায়।
3. First Column: প্রথম কলামের জন্য, কেবলমাত্র উপরের সেল থেকে আসা সম্ভব, তাই সেলের মান উপরের সেলের মান যোগ করে পাওয়া যায়।
4. Rest of the Grid: বাকি সেলগুলির জন্য, left এবং top থেকে আসা দুটি পাথের মধ্যে যেটি কম, সেটি যোগ করে সর্বনিম্ন পাথের সমষ্টি বের করা হয়।
5. শেষের কোঅর্ডিনেট (bottom-right) সেলটির মান হলো minimum path sum।

2. Grid Problem: Unique Paths

এটি একটি ক্লাসিক্যাল Grid Problem যেখানে, আমাদের m x n গ্রিডে top-left (0, 0) থেকে bottom-right (m-1, n-1) কোঅর্ডিনেটে পৌঁছানোর unique paths এর সংখ্যা বের করতে হবে, যেখানে আপনি কেবল right এবং down দিকেই চলতে পারেন।

2.1. Dynamic Programming Approach

এটি আবার একটি Dynamic Programming সমস্যা, যেখানে আমরা জানি যে, কোন সেলে পৌঁছানোর জন্য কতগুলো পথ রয়েছে, এবং সেই অনুযায়ী পরবর্তী সেলগুলোতে পৌঁছানোর পথ সংখ্যা হিসাব করা যাবে।

1. Subproblem: কোন সেলে পৌঁছানোর পথ সংখ্যা গণনা করতে, আপনি কেবলমাত্র top এবং left সেল থেকে আসতে পারবেন।
2. Recursive Formula: $$dp[i][j] = dp[i-1][j] + dp[i][j-1]$$ যেখানে dp[i][j] হল (i, j) সেলে পৌঁছানোর পথের সংখ্যা।

2.2. Java Code Implementation

public class UniquePaths {

    // Function to find the number of unique paths
    public int uniquePaths(int m, int n) {
        // Create a DP table
        int[][] dp = new int[m][n];

        // Initialize the first row and first column to 1
        for (int i = 0; i < m; i++) {
            dp[i][0] = 1; // Only one way to reach cells in the first column (going down)
        }

        for (int i = 0; i < n; i++) {
            dp[0][i] = 1; // Only one way to reach cells in the first row (going right)
        }

        // Fill the rest of the DP table
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1]; // Add the number of ways from top and left
            }
        }

        // The bottom-right cell contains the number of unique paths
        return dp[m - 1][n - 1];
    }

    public static void main(String[] args) {
        UniquePaths solver = new UniquePaths();
        System.out.println("Unique Paths: " + solver.uniquePaths(3, 7)); // Output: 28
    }
}

2.3. Explanation:

1. Base Case: প্রথম সারি এবং প্রথম কলামটির প্রতিটি সেলে 1 টি পথ থাকবে, কারণ আপনি কেবল right এবং down চলতে পারবেন।
2. DP Table: প্রতিটি সেলকে পূর্ণ করতে, আপনি তার top এবং left সেল থেকে পথ সংখ্যা যোগ করবেন।
3. শেষের সেল (bottom-right) হল সর্বোচ্চ সংখ্যক পথের সংখ্যা।

সারাংশ

Dynamic Programming grid problems সমাধান করতে একটি অত্যন্ত শক্তিশালী কৌশল। আমরা দুটি গ্রিড সমস্যার সমাধান দেখলাম:

1. Minimum Path Sum: এখানে, আমাদের একটি গ্রিডের মধ্যে সর্বনিম্ন পাথের সমষ্টি বের করার জন্য Dynamic Programming ব্যবহার করা হয়েছে।
2. Unique Paths: এখানে, top-left থেকে bottom-right কোঅর্ডিনেটে পৌঁছানোর মোট ইউনিক পথের সংখ্যা বের করা হয়েছে।

Dynamic Programming পদ্ধতি ইনপুট ডাটার বিভিন্ন সাবপ্রবলেমে কাজ করার মাধ্যমে পুনরাবৃত্তি সমস্যাগুলির সমাধান দ্রুত এবং কার্যকরীভাবে করতে সাহায্য করে।