# Pembahasan OSK 2015 No 6
###### tags: `osk` `dp` `combinatorics`

Definisikan $dp[x][y]$ sebagai banyaknya cara $x$ orang membelanjakan $y$ rupiah.

Kita mempunyai beberapa kasus:
1. Orang ke-$x$ memesan **nasi + lauk saja**
Berarti uang yang dibelanjakan oleh orang ke-$x$ sebesar $4+2=6$ ribu rupiah. Sehingga kasus ini ada $dp[x-1][y-6]$ cara
2. Orang ke-$x$ memesan **nasi + lauk + es cendol**
Berarti uang yang dibelanjakan oleh orang ke-$x$ sebesar $4+2+1=7$ ribu rupiah. Sehingga kasus ini ada $dp[x-1][y-7]$ cara
3. Orang ke-$x$ memesan **burger saja**
Berarti uang yang dibelanjakan oleh orang ke-$x$ sebesar $5$ ribu rupiah. Sehingga kasus ini ada $dp[x-1][y-5]$ cara
4. Orang ke-$x$ memesan **burger + es cendol**
Berarti uang yang dibelanjakan oleh orang ke-$x$ sebesar $5+1=6$ ribu rupiah. Sehingga kasus ini ada $dp[x-1][y-6]$ cara

Sehingga
$dp[x][y]=dp[x-1][y-6]+dp[x-1][y-7]+dp[x-1][y-5]+dp[x-1]+dp[y-6]$
$dp[x][y]=dp[x-1][y-5]+2 \times dp[x-1][y-6]+dp[x-1][y-7]$

---
## Mencari Basecase
- Ketika $y<0$, maka kita tidak dapat membelanjakan uang tersebut. Sehingga $dp[x][y]=0$ untuk $y<0$.
- Ketika $x=0$ dan $y>=0$, maka semua orang telah membelanjakan uang tersebut. Sehingga $dp[x][y]=1$ untuk $x=0$ dan $y>=0$.

---
## Relasi Akhir
- $dp[x][y]=dp[x-1][y-5]+2 \times dp[x-1][y-6]+dp[x-1][y-7]$
- $dp[x][y]=0$ untuk $y<0$
- $dp[x][y]=1$ untuk $x=0$ dan $y>=0$

---
## Tabel $dp[x][y]$
|x\y|1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 |
|---|--- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
1| 0 | 0 | 0 | 0 | 1 | 3 | 4 | 4 | 4 | 4 | 4 | 4 | 4 | 4 | 4 | 4 | 4 | 4 | 4 | 4 | 4 | 4 | 4 | 4 | 4 | 4 | 4 | 4 | 4 | 4 |
2| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 5 | 11 | 15 | 16 | 16 | 16 | 16 | 16 | 16 | 16 | 16 | 16 | 16 | 16 | 16 | 16 | 16 | 16 | 16 | 16 |
3| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 7 | 22 | 42 | 57 | 63 | 64 | 64 | 64 | 64 | 64 | 64 | 64 | 64 | 64 | 64 |
4| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 9 | 37 | 93 | 163 | 219 | 247 | 255 | 256 | 256 | 256 |
5| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 11 | 56 | 176 | 386 | 638 |

jawaban akhir ada di $dp[5][30]=638$ **(A)**