DYNAMIC PROGRAMMING (กำหนดการพลวัต)

 

Dynamic Programming (กำหนดการพลวัต) : 

            Dynamic Programming หรือที่เรารู้จักกันในชื่อของ DP เป็นเทคนิคที่สำคัญมากใน Competitive Programming โดย DP นั้นจะเป็นสิ่งที่เราใช้หาสิ่งหาคำตอบที่ดีที่สุดในสิ่งที่เราต้องการจะหา โดยการที่จะทำ DP นั้นเราจำเป็นที่จะต้องใช้สถานะ(State) เข้ามาช่วย โดยในตอนแรกเราจำเป็นที่จะต้องนิยาม State สถานะให้ชัดเจน อย่างเช่น dp[i][j] แทน จำนวนเหรียญหรือธนบัตรที่จะต้องใช้น้อยที่สุด ในการแลกเป็นเงิน j โดยใช้เงินหรือธนบัตรตั้งแต่อันที่้ 1 ถึง i (Coin Change Problem) โดยปัญหาที่เราได้กล่าวมานี้เราคงเคยได้เห็นกันมาแล้วในเรื่องของ Recursive Function ที่เคยได้กล่าวไปในโพสต์ที่เรา แต่ตอนนี้จะขอสาธิตวิธีการใช้ DP ในการแก้ปัญหา

            ในตอนแรกเราจำเป็นที่จะต้องประกาศตัวแปรให้ชัดเจนก่อน โดยขอให้ dp[i][j] มีนิยามเหมือนสิ่งที่เคยได้กล่าวมาก่อนหน้านี้ และขอให้ coin[i] แทน ค่าของเหรียญที่ i

            จากนั้นเราจะต้องหา Recurrence Relation ระหว่างสถานะ โดยจากการสังเกตเราจะพบว่า dp[i][j] = min(dp[i][j-coin[i]], dp[i-1][j] 

            และก็เขียนโค้ดก็จะเป็นอันเสร็จ 

ตัวอย่าง : 

int solve(int coin[], int n, int want){

        int dp[n+1][want+1]; // base 1

        memset(dp, 0x3f, sizeof(dp)); // set to infinity

        for(int i = 1; i <= n; ++i){

                for(int j = 1; j <= want; ++j){

                        dp[i][j] = min(dp[i][j-coin[i]]+1, dp[i-1][j]);

                }

        }

        return dp[n][want];

}