Basic Dynamic Programming(Part 1)

Written by Ahnaf Shahriar Asif on June 28, 2019

Dynamic Programming

Introduction

আমরা ডাইনামিক প্রোগ্রামিংয়ের সাথে মোটামুটি সবাই পরিচিত। আজকে ডিপি নিয়ে কিছু বেসিক আলোচনা করবো। আশা করি উপকারে আসবে। তবে পোস্টটি অবশ্যই সবার জন্য না, যারা ডিপি কিছুটা পারেন কিন্তু প্রব্লেম সল্ভ করতে কষ্ট হচ্ছে বা কীভাবে প্রব্লেম অ্যাপ্রোচ করতে হবে সেটা বুঝে উঠতে পারছেন না, পোস্টটি তাদের জন্য। আশা করি এই পোস্টটি ভালো করে বুঝে পড়লে সমস্যাগুলোর সমাধান কিছুটা সহজ হয়ে যাবে। আমি এখানে স্ট্রাটেজি নিয়েও কিছু কথা বলার চেষ্টা করবো, যদিও এই জিনিসগুলো সবারই জানা থাকার কথা।

কেনো প্রব্লেম ডিপি দিয়ে সল্ভ করা যাবে কিনা সেটা বোঝা মোটামুটি সহজ। প্রাথমিক দিকে সহজ ডিপি প্রব্লেমগুলােতে সাধারণত তোমাকে কিছু সংখ্যা বা কিছু শর্ত দিয়ে কিছু একটা করা যায় কিনা, বা কিছু একটা মিনিমাইজ করা বা ম্যক্সিমাইজ করার জন্য বলতে পারে। বা হয়তো কোনো একটি কাজ কয়ভাবে করা যায় বা ধরা যাক একটা কাজ অনেকভাবে করা যায়, তার মধ্যে কোনভাবে করলে সবথেকে বেশি লাভ হবে এরকম কিছু বেড় করতে বললে সেটা ডিপি দিয়ে করা যেতে পারে। সত্যি কথা বলতে গেলে ডিপি দিয়ে হয়তো প্রায় সবকিছুই করা সম্ভব, কারণ ডিপি মূল ধারণাটি হচ্ছে সকল ভাবে চিন্তা করে দেখবো আর তার মধ্যে সবথেকে ভালো সলিউশনটি নিয়ে নিব । অর্থাৎ, এটি একদমই ব্রুটফোর্স টেকনিক,কিন্তু আমরা একটু চালাকি করে ব্রুটফোর্স করবো যাতে কোনো কিছু একবারের বেশি হিসাব করার দরকার না পরে। আমি এই কথাটি দিয়ে কি বোঝাচ্ছি সেটা না বুঝলে এই পোস্টটি পড়ে দেখো, তারপর সামনের দিকে আগাও।

DP States

ডিপি স্টেট নিয়ে আমি প্রাথমিক কথাগুলো বলছিনা, এখানে দেখে নিতে পারো। আমরা ডিপি এর স্টেট কি, এটার কাজ কি, এগুলো জানি। এবার আমরা জানবো কীভাবে ডিপি স্টেটগুলো বেড় করা যায়। প্রথম কথা হচ্ছে যার এক্সপেরিয়েন্স যত বেশি সে তত তাড়াতাড়ি স্টেট বেড় করতে পারে। আর একবার ডিপির স্টেট বেড় করতে পারলে আমাদের প্রব্লেম সল্ভ করা কোনো ব্যাপারই না। ডিপির স্টেট বেড় করতে গেলে আমাদেরকে একটু সুন্দর করে চিন্তা করতে হবে। প্রব্লেম পড়ার পর নিচের জিনিসগুলো ভালো করে খেয়াল করো:

প্রব্লেমটি কী?
আমাকে কী কী দেয়া হয়েছে?
আমাকে কী কী বেড় করতে হবে?
আমি যা যা পেয়েছি সেগুলো থেকে আরও কী কী পাওয়া সম্ভব?

উপরের জিনিসগুলো কীভাবে অ্যাপ্রোচ করতে হবে তা একটা প্রব্লেমের মাধ্যমে দেখাচ্ছি।

Problem 1

তোমাকে \(n\) টি সিঁড়ি দেয়া আছে। তুমি \(1\) নাম্বার সিঁড়িতে আছো, তোমাকে \(n\) তম সিড়িঁতে যেতে হবে। তুমি চাইলে এক স্টেপ সামনে যেতে পারো, অথবা দুই স্টেপ। অর্থাৎ, তুমি যদি \(1\) নাম্বার সিড়িঁতে থাকো তাহলে সেখান থেকে তুমি \(2\) বা \(3\) নাম্বার সিড়িঁতে যেতে পারবে। এখন তোমাকে বলতে হবে তুমি কতভাবে \(1\) থেকে \(n\) তম সিড়িঁতে যেতে পারবে।

যদিও প্রব্লেমটি খুবই সহজ, তবুও এখানে আমরা প্রব্লেমটি ধাপে ধাপে সমাধান করার চেষ্টা করবো। প্রথমেই আমাদেরকে প্রব্লেমটি বুঝতে হবে। এখানে প্রব্লেমটা অনেকটাই পরিষ্কার। আমাকে 1 থেকে n পর্যন্ত যেতে হবে, কতভাবে যেতে পারবো সেটা বেড় করতে হবে। আমাদের ডিপি প্রব্লেম দেখার পর প্রথম কাজ হবে স্টেট বেড় করা। আমরা এখন স্টেট বেড় করবো এই প্রব্লেমে। এখানে খুব ভালো করে চিন্তা করো। ধরো আমরা x তম সিড়িঁতে আছি। এই x তম সিড়িঁতে কতভাবে আসা যাবে সেটা কিসের কিসের উপর নির্ভর করছে? x এর মান কত, তার উপর আমাদের উত্তর নির্ভর করছে। তাহলে একটা স্টেট হবে x, অর্থাৎ আমরা কোথায় আছি সেটা আমাদের সমস্যার সমাধান করার জন্য প্রয়োজন পড়বে। আর কোনো কিছু কি দরকার পরছে আমাদের? আর কিছু আমাদের এখানে দরকার পড়বে না। কারণ কততম সিড়িঁতে কতভাবে আসা যায় এটা জানলেই আমাদের হয়ে যাচ্ছে। তাহলে আমাদের একটি অ্যারে, \(dp(n)\) রাখলেই হয়ে যাচ্ছে। যেখানে \(dp(i) = number\ of\ ways\ to\ reach\ i\) । এখন আমরা x তম সিড়িঁতে কোন ক‌োন সিড়িঁ থেকে আসতে পারবো? \(x-1\) আর \(x-2\) তম সিড়িঁ থেকে, তাই না? তাহলে আমরা x তম সিড়িঁর জন্য উত্তরটি \(x-1\) আর \(x-2\) তম সিড়িঁর উত্তর থেকে জানতে পারি। অন্যভাবে বলা যায়, \(dp(x) = dp(x-1)+dp(x-2)\) কারণ আমরা যতভাবে \(x-1\) আসতে পারি ততভাবে এক স্টেপ আগালে আমরা x এ আসতে পারবো, আবার \(x-2\) এ যতভাবে আসতে পারি, ততভাবে দুই স্টেপ আগালে আমরা x এ আাসতে পারবো। তাহলে আমরা \(dp(x-1)\) আর \(dp(x-2)\) থেকে \(dp(x)\) বেড় করতে পারছি, আগের মানগুলো ব্যাবহার করে পরের গুলো বেড় করা সম্ভব হচ্ছে। এভাবে রিকার্সিভলি চিন্তা করলে দেখতে পাবে খুব শুরুর দিকের কিছু মান হাতে হাতে বেড় করে ফেলতে পারলে বাকি মানগুলো খুব সহজেই লুপ চালিয়ে বেড় করা যায়। এখানে আমরা \(dp(0)\) আর \(dp(1)\) বেড় করতে পারলেই হবে। কারণ \(dp(2) = dp(1)+dp(0)\) , বাকিগুলোও লুপ দিয়েই করা যাবে। এখন চিন্তা করো \(dp(0)\) এর মান কি হবে। আমরা 0 তম সিড়িঁতে এখন দাড়িঁয়ে আছি, আলাদা করে সেখানে কখনোই যাবোনা। তাহলে আমরা 0 তম সিড়িঁতে একভাবে যেতে পারি, সেটা হলো না যাওয়া. তাহলে \(dp(0) = 1\) । এবার আসি \(dp(1)\) এ। আমরা \(dp(1)\) এ একভাবেই আসতে পারব‌ো, সেটা হচ্ছে 0 তম সিড়িঁ থেকে এক স্টেপ নিয়ে 1 তম সিড়িঁতে যাবো। তাহলে \(dp(1) = dp(0)\) । কিন্তু আমরা বাকি সিড়িঁগুলোতে ঠিক আগের সিড়িঁ বা ২ ঘর আগের সিড়িঁ থেকে আসতে পারবো। হয়ে গেলো! এবার \(dp(n)\) হচ্ছে আমাদের উত্তর। এর টাইম কম্প্লেক্সিটি \(O(n)\) কোড দেয়ার দরকার নেই, তাও নিচে দিয়ে দিচ্ছিঃ

dp[0] = dp[1] = 1;
for(int i = 2; i <= n;i++){
    dp[i] = dp[i-1]+dp[i-2];
}
printf("Answer is: %d\n",dp[n]);

Variant 1

এখন যদি বলি আমরা সর্বোচ্চ k সাইজের জাম্প দিতে পারবো, অর্থাৎ, আমরা x তম সিড়িঁ থেকে \(x+1,x+2,....,x+k\) তম সিড়িঁর যেকনো সিড়িঁতে যেতে পারবো, তাহলে কেমন হবে ব্যাপারটা? নিচে রিকার্সিভ ফর্মুলাটা দিয়ে দিচ্ছি, না বুঝলে আবার চিন্তা করে দেখো:

\[dp(x) = \sum_{i = 1}^{k} dp(x-i)\]

এটির কম্প্লেক্সিটি \(O(n \times k)\)। কম্প্লেক্সিটি কীভাবে হিসাব করছি, সেটা না বুঝলে এই ব্লগটি পড়ে দেখতে পারো। এটি সেগমেন্ট ট্রি ব্যবহার করে সহজেই \(O(n\log n)\) এ করা যায়, কিন্তু সেটা এখানে আলোচনা না করাই ভালো।

Variant 2

এখন শেষ প্রব্লেমটিকে একটু কঠিন করা যাক। প্রব্লেমের সব ঠিক থাকবে, শুধু একটা নতুন শর্ত জুড়ে দিচ্ছি। তুমি একই মুভ(move) একটানা একাধিকবার দিতে পারবেনা। অর্থাৎ, ধরো তুমি 1 স্টেপ নিয়ে 4 থেকে 5 নাম্বার সিড়িঁতে গেলে । এখন তুমি আর 1 স্টেপ নিয়ে 5 থেকে 6 এ যেতে পারবেনা। যেহেতু ঠিক আগেরবার তুমি 1 নাম্বার মুভটি ব্যবহার করে ফেলেছো, তুমি এবার 1 নাম্বার মুভ ছাড়া বাকিগুলো ব্যবহার করতে পারবে। অর্থাৎ, একই ধরণের মুভ একটানা দিতে পারবেনা, 1-1-2 এই মুভটি দিতে পারবেনা, কারণ 1-1 একসাথে পড়ে যাচ্ছে, কিন্তু 1-2-1 মুভ দিতে পারবে, যেহেতু কোনো পাশাপাশি মুভ সমান না। এবার তোমাকে বেড় করতে হবে কতভাবে n এ যাওয়া যায়।

এখানে লক্ষ্য করো, শুধু কোন ইন্ডেক্সে আছি, সেটাই বড় কথা নয়, আমরা সর্বশেষ কোন মুভ দিয়েছি সেটাও এখানে গুরুত্বপূর্ণ ভূমিকা পালন করছে। তাই আমরা সেটাও স্টেট হিসেবে রাখবো। অর্থাৎ, \(dp(R,S)\) এর মানে হলো আমরা R তম পজিশনে আছি আর S তম মুভ দিয়েছি । তাহলে শেষ মুভ কি ছিল, এটা আমরা রেখে দিলাম। এখন শুধু আগের স্টেট গুলোর ওই মুভ ছাড়া বাকিগুলো \(dp(R,S)\) এ যোগ করে দিব। আর ফাইনাল উত্তর হবে \(\sum_{i = 1}^{k} dp(n,i)\) । নিচে কোডটি দিয়ে দিলাম:

int ans = 0;
for(int i = 1; i <= n;i++){
    for(int j = 1; j <= k;j++){
        //dp[i][j] তে শুধু তাদেরকেই যোগ করবো যাদের শেষ মুভ j নয়। 
        for(int x = 1; x <= k;x++){
            if(i-x >= 0 and x != j)dp[i][j] += dp[i-x][x];
        }
    }
}
for(int i = 1; i <= k;i++)ans += dp[n][i];
printf("The Answer Is: %d\n",ans);

এই কোডের কম্প্লেক্সিটি \(O(n\times k^2)\) ।

এখন সামনের দিকে যাওয়ার আগে Knapsack,coin change,rock climbing,LIS,LCS একটু দেখে নাও।

Problem 2

তোমাকে \(n \times m\) সাইজের একটা গ্রিড দেয়া আছে। তোমাকে \((0,0)\) থেকে \((n-1,m-1)\) সেলে যেতে হবে। কিন্তু শর্ত হচ্ছে তুমি শুধুমাত্র ডানে বা নিচে যেতে পারবে। আর কিছু সেল ব্লক করা থাকবে, যেগুলোতে তুমি যেতে পারবেনা। তুমি কতভাবে \((0,0)\) থেকে \((n-1,m-1)\) সেলে যেতে পারবে?

এখন, এই প্রব্লেমটা সল্ভ করবো কীভাবে? প্রথম কথা, আমরা কোথায় আছি, সেটা খুবই গুরুত্বপূর্ণ। তাই আমাদের স্টেটে সেলের পজিশন রাখতে হবে। আর কিছু কি রাখতে হবে? আমরা ওই সেলে কতভাবে আসতে পারছি সেটাই মূল বিষয়, তাই না? এজন্যই আমাদের ডিপির স্টেট হবে শুধু তার সেল, অর্থাৎ, রো(row) আর কলাম(column)। তাহলে \(dp(n,m)\) হলো আমাদের টেবিল আর এখানে \(dp(S,R) = x\) হলে,\((0,0)\) থেকে \((S,R)\) সেলে \(x\) ভাবে আসা যায়। এখন আগের প্রব্লেমটার মতো চিন্তা করো। আমরা \((S,R)\) সেলে কোন কোন যায়গা থেকে আসতে পারবো ? ঠিক উপরের সেল অথবা বামের সেল থেকে, তাই না? অর্থাৎ, উপরের সেল আর বামের সেলের উপয়ের যোগফলই হলো আমাদের সেলের মোট উপায়ের সংখ্যা। সুতরাং, \(dp(S,R) = dp(S-1,R)+dp(S,R-1)\) । আর আগের মতোই, \(dp(0,0) = 1\) । এবার কোডটা দেখে ফেলি।

// here function ok(a,b) means cell (a,b) exists and it's not blocked
dp[0][0] = 1;
for(int i = 0; i < n;i++){
    for(int j = 0; j < m;j++){
        if(ok(i,j)){
            if(ok(i-1,j))dp[i][j] += dp[i-1][j];
            if(ok(i,j-1))dp[i][j] += dp[i][j-1];
        }
    }
}
printf("Answer is: %d\n",dp[n-1][m-1]);

Variant 1

এবার আবার প্রব্লেমটাকে আগের মতো একটু কঠিন করে দেই। তুমি একই ধরণের মুভ একটানা একটার বেশি দিতে পারবেনা। অর্থাৎ, তুমি একই সাথে দুই বা তার বেশিবার নিচে নামতে পারবেনা বা ডানে যেতে পারবেনা। অনেকটা আগের প্রব্লেমের মতোই।

এখন কী করবো আমরা? চিন্তা করে দেখো, আমরা যদি আগের মতোই সর্বশেষ মুভ কোনটা দিয়েছি সেটা জানি, তাহলেই হয়ে যাবে। আমরা উপর থেকে নিচে নামাকে 0 আর বাম থেকে ডানে যাওয়াকে 1 দিয়া প্রকাশ করতে পারি। তাহলেই হয়ে গেল। তাহলে আমাদের টেবিলটি হবে \(dp(2,n,m)\) । এখানে \(dp(0 , p , q)\) মানে আমরা উপর থেকে নিচে নেমেছি, আর \(dp(1 , p , q)\) মানে আমরা বাম থেকে ডানে গিয়েছি। নিচে কোডটি দিয়ে দিচ্ছি।

for(int i = 0; i < n;i++){
    for(int j = 0; j < m;j++){
        if(ok(i,j)){
            if(ok(i-1,j)){
                dp[0][i][j] += dp[1][i-1][j];
                dp[1][i][j] += dp[0][i-1][j];
            }
            if(ok(i,j-1)){
                dp[0][i][j] += dp[1][i][j-1];
                dp[1][i][j] += dp[0][i][j-1];
            }
        }
    }
}
printf("Answer is: %d\n",max(dp[0][n-1][m-1],dp[1][n-1][m-1]));

Variant2

এবার প্রব্লেমটাকে আরও কঠিন করা যেতে পারে। ধরো আমরা একসাথে সর্বোচ্চ K বার নিচে বা ডানে যেতে পারবো। তখন কি করবো? তখন উত্তরটি হবে এরকমঃ \(dp(x,y) = \sum_{i=1}^{k} dp(x-i,y) + \sum_{i = 1}^{k} dp(x,y-i)\) । আর এই ভেরিয়েশনে যদি বলে একই মুভ একবারের বেশি দিতে পারবোনা, তাহলে শেষ মুভ কি দিয়েছি সেটাও রাখতে হবে আরকি, তখন টেবিলটি হবে \(dp(k,x,y)\) ।

এখন সামনে যাওয়ার আগে নিচের প্রব্লেমগুলো সমাধান করে ফেলো:

Practice Problems

Important Tip:

আমরা তো ডিপি টেবিলে এক বা একাধিক স্টেট রাখতে শিখে গেছি, তাই না? \(dp(n,m)\), \(dp(n,m,k)\) ইত্যাদি। কিন্তু এই ডাইমেনশনগুলো কোন অর্ডারে নিচ্ছি সেটা কিন্তু প্রব্লেম সল্ভিংয়ে কোনো প্রভাব ফেলছে না, তাই না? যেমন এই প্রব্লেমটা দেখো, এখানে আমরা \(dp(2,n,m)\) নিয়েছিলাম, এখানে যদি \(dp(n,m,2)\) নিতাম তাহলে কি প্রব্লেম সল্ভ করা যেত না? অবশ্যই যেত! কিন্তু একটা গুরুত্বপূর্ণ কথা মনে রাখবে, কম্পিউটার \(dp(i,j)\) থেকে \(dp(i,j+1)\) যে সময় নেয়, \(dp(i,j)\) থেকে \(dp(i+1,j)\) তে যেতে তার থেকে বেশি সময় নেয়। অর্থাৎ কম্পিউটার অ্যারের ইনডেক্সগুলো ভার্টিকালি(উপর থেকে নিচে) এক্সেস করার থেকে হরিজন্টালি(ডান থেকে বামে) এক্সেস খুব দ্রুত করতে পারে। তাই ডিপি এর স্টেটগুলো ক্রমবর্ধমানে সাজালে সময় সবথেকে কম লাগে। এজন্যই \(dp(2,n,m)\) নিয়ে কাজ করা \(dp(n,m,2)\) নিয়ে কাজ করার থেকে ভালো। এটা সবসময় মাথায় রাখবে। অনেক সময় এধরণের অপটিমাইজেশন দরকার পড়ে।

Problem 3

তোমাকে একটি অ্যারে দেয়া আছে। প্রত্যেকটি ইন্ডেক্সে কিছু করে ভ্যালু আছে। তোমাকে ওই অ্যারে থেকে এমন কিছু ইন্ডেক্স বেড় করতে হবে যেন তাদের ভ্যালুর যোগফল সর্বোচ্চ হয়। কিন্তু একটা শর্ত আছে। তুমি পাশাপাশি দুটি ভ্যালু নিতে পারবেনা। অর্থাৎ, তুমি x তম ইন্ডেক্স বাছাই করলে \(x+1\) বা \(x-1\) তম ইন্ডেক্স নিতে পারবেনা।

এই প্রব্লেমটা ওই আগের মতোই ধাপে ধাপে সল্ভ করবো আমরা। প্রথমেই দেখবো স্টেট কি কি হতে পারে। আমরা কোন ইন্ডেক্সে আছি সেটা দরকার পরবে, তাই সেটা একটা স্টেট। আবার আমরা বর্তমান ইন্ডেক্সকে নিব নাকি নিবনা, এটাও দরকারি, তাই এই জিনিসটাও আমাদের মাথায় রাখতে হবে। তাহলে আমাদের ডিপি টেবিল হবে \(dp(2,n)\) । আমরা প্রত্যেক ইন্ডেক্সে যাব, একবার ওই ইন্ডেক্সকে নিয়ে, আবার না নিয়ে দেখবো কোনটা ম্যাক্সিমাম হয়। এখন যদি আমরা বর্তমান ইন্সেক্সকে ইনক্লুড না করি, তাহলে আগের ইন্ডেক্সকে নিলেও চলবে, না নিলেও চলবে। তাই, \(dp(0,x) = max \left \{ dp(0,x-1),dp(1,x-1)\right \}\) । কিন্তু আমরা যদি বর্তমান ইন্ডেক্সকে ইনক্লুড করি তাহলে আমরা আগের ইন্ডেক্স নিতে পারবোনা। তাই , \(dp(1,x) = ara(x)+dp(0,x-1)\) । তাহলে আমাদের উত্তর হবে \(max \left \{ dp(0,n-1),dp(1,n-1)\right \}\) । কোডটি নিচে দিয়ে দিচ্ছি।

int n;
scanf("%d",&n);
for(int i = 0; i < n;i++)scanf("%d",&ara[i]);

dp[0][0] = 0; // we're not including ara[0] here
dp[1][0] = ara[0]; // we're including ara[0] here 
for(int i = 1; i < n;i++){
    dp[0][i] = max(dp[0][i-1],dp[1][i-1]);
    dp[1][i] = ara[i]+dp[0][i-1];
}
printf("Answer is: %d\n",max(dp[0][n-1],dp[1][n-1]));

Practice Problems

উপরের সমস্যাগুলো বুঝে বুঝে সমাধান করতে পারলে তোমাদের বেসিক ডিপির সবকিছুই হয়ে যাবে আশা করি। এরপরের পোস্টগুলোতে আমরা দেখবো কীভাবে আরও দারুন দারুন অবজারভেশন ব্যাবহার করে মজার মজার ডিপি প্রব্লেম সল্ভ করা যায়।

Programming Throwdown

Competitive Programming in Bengali