---
title: 爬樓梯問題(DP)
tags: DP
robots: noindex, nofollow
langs: zh
---
# 爬樓梯問題

### Q1:(classic)
樓梯有$n$階，小明一步可以爬一或兩階
請問有幾種方法？

### A1:
定義狀態：$A_{n}$為爬到$n$階的方法數

遞迴式：$A_n = A_{n-1} + A_{n-2}$

時間複雜度：$O(n)$

### Q2:
樓梯有n階，小明一步可以爬一或兩階**或四階或五階**
請問有幾種方法？

### A2:
定義狀態：$A_n$為爬到$n$階的方法數

遞迴式：$A_n = A_{n-1} + A_{n-2} + A_{n-4} + A_{n-5}$

時間複雜度：$O(n)$

### Q3:
樓梯有n階，小明一步可以爬一或兩階
給每階的過路費，第i階過路費為$C_i$
請問走到第n階的最小花費？

### A3:
給個函式：$\min(a,b)$為$a$,$b$較小數字

定義狀態：$A_n$為走到第n階的最小花費

遞迴式：$A_n$ = $C_n+\min(A_{n-2}, A_{n-1})$

時間複雜度：$O(n)$

### Q4:
樓梯有n階，小明一步可以爬一或兩階
給每階的過路費，第i階過路費為$C_i$
求走到第n階花費的**個位數**最小？

### A4:
增維：加個維度ㄅ

定義狀態：$if(A_{nm})$為第n階個位數為m是否有可能

pseudocode:

//code 貼這兒
for (m=0; m<10; m++) {
    if(A[n-1][m] == 1)A[n][(m + Cn)%10] = 1;
    if(A[n-2][m] == 1)A[n][(m + Cn)%10] = 1;
}
for (i=0;i <10; i++) {
    if (A[n][i] == 1) {
        cout << i;
        break;
    }
}

時間複雜度：

# 隆重介紹DP
DP = 遞迴+記錄下曾經算過的部分
把問題轉化成遞迴問題，用陣列儲存的方式優化速度！
TopDown: 認真做遞迴，認真把傳進去的參數當作陣列的位置存放
BottomUp: 用迴圈去填完表，再查詢**（建議）**