একটি ট্রায়্যাঙ্গেল (২D ভেক্টর) দেওয়া। উপরের রো থেকে নিচের রোতে আডজেসেন্ট নম্বরে যেতে হবে। ন্যূনতম পাথ সম বের করতে হবে।
উদাহরণ: [[2],[3,4],[6,5,7],[4,1,8,3]] → ১১ (2+3+5+1)।
সমাধানের ধাপসমূহ
- বটম-আপ DP: নিচের রো থেকে উপরে যান।
- DP অ্যারে = শেষ রো কপি করুন।
- প্রতিটি রো i-তে:
dp[j] = triangle[i][j] + min(dp[j], dp[j+1])। - শেষে
dp[0]রিটার্ন করুন।
C++ উদাহরণ
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int minimumTotal(vector<vector<int>>& triangle) {
vector<int> dp = triangle.back();
for (int i = triangle.size() - 2; i >= 0; i--) {
for (int j = 0; j <= i; j++) {
dp[j] = triangle[i][j] + min(dp[j], dp[j+1]);
}
}
return dp[0];
}
};
int main() {
Solution ob;
vector<vector<int>> v = {{2},{3,4},{6,5,7},{4,1,8,3}};
cout << ob.minimumTotal(v);
}
ইনপুট
[[2],[3,4],[6,5,7],[4,1,8,3]]
আউটপুট
11
