# Hint Latihan Dynamic Programming

## A - Recursion: Davis' Staircase

Misalkan $f(n)$ adalah banyaknya cara menuju ke anak tangga ke-n

Asumsi dia berada di lantai dan bisa dianggap anak tangga ke-0

Untuk sampai pada anak tangga ke-n, ada 3 kemungkinan :
* loncatan terakhir sejauh 1, artinya ia perlu pergi ke anak tangga ke-(n-1) dulu -> banyak cara = $f(n-1)$
* loncatan terakhir sejauh 2, artinya ia perlu pergi ke anak tangga ke-(n-2) dulu -> banyak cara = $f(n-2)$
* loncatan terakhir sejauh 3, artinya ia perlu pergi ke anak tangga ke-(n-3) dulu -> banyak cara = $f(n-3)$

Sehingga,

$f(n) = f(n-1)+f(n-2)+f(n-3)$

$f(0) = 1$

$f(1) = 1$

$f(2) = 2$

## B - The Triangle

Perhatikan array untuk menampung segitiga bilangan

a[1][1]
a[2][1] a[2][2]
a[3][1] a[3][2] a[3][3]
a[4][1] a[4][2] a[4][3] a[4][4]
....
a[n][1] a[n][2] a[n][3]  . . .  a[n][n]

Misal $f(n,m)$ adalah total bilangan maksimal yg diperoleh jika kita mulai dari bilangan di baris $n$ dan kolom $m$ atau posisi $(n,m)$

Dari posisi $(n,m)$ kita akan mendapatkan bialngan $a[n][m]$ dan bisa loncat ke 2 tempat :
* Jika loncat ke posisi $(n+1,m)$, maka berikutnya kita akan mendapatkan total maksimal $f(n+1,m)$
* Jika loncat ke posisi $(n+1,m+1)$, maka berikutnya kita akan mendapatkan total maksimal $f(n+1,m+1)$

Sehingga,

$f(n,m) = a[n][m] + max(f(n+1,m), f(n+1,m+1))$
jika n baris terakhir, maka $f(n,m) = a[n][m]$

## C - Typical Stairs

Misal $f(n)$ = banyaknya cara ke pijakan ke-n

Jika pijakan ke-n rusak, maka
$f(n) = 0$
Jika pikanan ke-n tidak rusak, maka
$f(n) = f(n-1) + f(n-2)$

## D - Mashmokh and ACM

Misal $f(n, k)$ = banyaknya barisan sepanjang k yang suku terakhirnya adalah n

Perhatikan bahwa suku kedua terakhir haruslah faktor dari n. Untuk melengkapinya, kita perlu membuat barisan sepanjang k-1 dengan suku terakhirnya adalah faktor dari n.

$f(n, k) = f(d_1, k-1) + f(d_2, k-1) + f(d_3, k-1)...$

dimana $d_1, d_2, d_3, ...$ adalah faktor dari n