C++-এ পেইন্ট হাউস II (Paint House II) সমস্যা সমাধান

ধরি আমাদের nটি ঘর একটি সারিয়ে আছে। প্রতিটি ঘর kটি রঙের যেকোনো একটি দিয়ে রঙ করা যাবে। প্রতিটি ঘরকে নির্দিষ্ট রঙ দিয়ে রঙ করার খরচ ভিন্ন। আমাদের সব ঘর রঙ করতে হবে যাতে কোনো দুটি আঁচবিক ঘরের রঙ একই না হয়।

রঙ করার খরচ একটি n x k ম্যাট্রিক্স দিয়ে দেওয়া থাকে। আমাদের সব ঘর রঙ করার ন্যূনতম খরচ বের করতে হবে।

উদাহরণস্বরূপ, খরচ ম্যাট্রিক্স:

1	5	3
2	9	4

আউটপুট হবে 5, কারণ ঘর 0 কে রঙ 0, ঘর 1 কে রঙ 2 দিয়ে রঙ করলে খরচ 1+4=5। অথবা ঘর 0 কে রঙ 2, ঘর 1 কে রঙ 0 দিয়ে খরচ 3+2=5।

সমাধানের ধাপসমূহ

n := costs.size(), m := costs[0].size()
ret := INF
i = 1 থেকে n-1:
- req := INF
- দুটি অ্যারে lmins এবং rmins আকার m
- lmins[0] = costs[i-1][0], rmins[m-1] = costs[i-1][m-1]
- j = 1 থেকে m-1: lmins[j] = min(costs[i-1][j], lmins[j-1])
- j = m-2 থেকে 0: rmins[j] = min(costs[i-1][j], rmins[j+1])
- j = 0 থেকে m-1:
  - left = (j-1 >= 0 ? lmins[j-1] : INF)
  - right = (j+1 < m ? rmins[j+1] : INF)
  - costs[i][j] += min(left, right)
i = 0 থেকে m-1: ret = min(ret, costs[n-1][i])
ফেরত: (ret == INF ? 0 : ret)

প্রোগ্রাম উদাহরণ

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int minCostII(vector>& costs) {
        int n = costs.size();
        int m = n ? costs[0].size() : 0;
        int ret = INT_MAX;
        for (int i = 1; i < n; i++) {
            int req = INT_MAX;
            vector lmins(m);
            vector rmins(m);
            lmins[0] = costs[i - 1][0];
            rmins[m - 1] = costs[i - 1][m - 1];
            for (int j = 1; j < m; j++) {
                lmins[j] = min(costs[i - 1][j], lmins[j - 1]);
            }
            for (int j = m - 2; j >= 0; j--) {
                rmins[j] = min(costs[i - 1][j], rmins[j + 1]);
            }
            for (int j = 0; j < m; j++) {
                int left = j - 1 >= 0 ? lmins[j - 1] : INT_MAX;
                int right = j + 1 < m ? rmins[j + 1] : INT_MAX;
                costs[i][j] += min(left, right);
            }
        }
        for (int i = 0; i < m; i++) {
            ret = min(ret, costs[n - 1][i]);
        }
        return ret == INT_MAX ? 0 : ret;
    }
};

int main() {
    Solution ob;
    vector> v = {{1,5,3},{2,9,4}};
    cout << (ob.minCostII(v));
}

ইনপুট

{{1,5,3},{2,9,4}}