Dynamic Programming - 1 ( Coin change )

একটা বড় problem কে ছোট ছোট ভাগে ভাগ করে সেগুলো solve করার মাধ্যমে বড় problem টাকে solve করাই হচ্ছে Dynamic programming এর কাজ। আমরা প্রথমে কিছু সহজ DP প্রবলেম শিখব। আমরা আজকে যা শিখব তা হল coin change টাইপ প্রবলেম।

Type -1 ( Unlimited Coin )

শিখব কই থেকেঃ

See this slide

#define MAX 10000

vector<int>coin; // contains coin value
int is_possible[MAX];
int coin_need[MAX];

int coin_change(int need_to_make) // need_to_make < MAX
{
    // fill coin_need with INF value here

    is_possible[0] = 1;
    coin_need[0] = 0;

    for(int i=0;i<coin.size();i++)
    {
        for(int j=0;j+coin[i]<MAX;j++)
        {
            if(is_possible[j])
            {
                int next = j+coin[i];

                is_possible[ next ] = 1;
                coin_need[ next ] = min( coin_need[j]+1 , coin_need[ next ] );
            }
        }
    }
    return coin_need[need_to_make];
}

Type - 2 ( Limited Coin )

এখন তোমাকে যদি কিছু coin দেয়া হয় এবং বলে দেয়া হয় কোন coin টা maximum কয়বার ব্যবহার করতে পারবে তখন কি করবে?

আমরা unlimited  coin  এর জন্যে যেভাবে বাম থেকে ডানে লুপ চালিয়েছি, এবার একই ভাবে ডান থেকে বামে লুপ চালাব। তাহলেই limited coin এর জন্যে answer পেয়ে যাব।

#define MAX 10000

struct coin{
    int val,how_many;
};

vector<coin>has_coin;
bool is_possible[MAX];
int minimum_coin_need[MAX];


int limited_coin_change(int need_to_make)
{
    is_possible[0] = true;
    minimum_coin_need[0] = 0;

    for(int i=0;i<has_coin.size();i++)
    {
        for(int j= MAX-1 ; j>=0 ; j--)
        {
            if(is_possible[j] == true)
            {
                int value = has_coin[i].val;
                int next = j + value;
                int curent = j;

                for(int k=0;k<has_coin[i].how_many;k++)
                {
                    is_possible[next] = true;
                    minimum_coin_need[next] = min(minimum_coin_need[curent]+1,minimum_coin_need[next]);

                    curent = next;
                    next = next+value;
                }
            }
        }
    }

    return minimum_coin_need[need_to_make]; // return desire result
}

Problem

UVA - 147, 166, 357, 674, 10313, 10306, 11137, 11517, 562

Lightoj - 1231, 1232, 1233