因為上樓和下樓是?個可逆的過程，因此我們可以把下樓問題轉化成上到第n個臺階，?共有多少種?案。
解法：動態規劃

1. 狀態表?：
   dp[i] 表?：?到第i 個臺階的總?案數。
   那最終結果就是在dp[n]處取到。
2. 狀態轉移?程：
   根據最后?步劃分問題，?到第i 個臺階的?式有三種：
   a. 從i - 1 臺階向上?1 個臺階，此時?到i 臺階的?案就是dp[i - 1] ；
   b. 從i - 2 臺階向上?2 個臺階，此時?到i 臺階的?案就是dp[i - 2] ；
   c. 從i - 3 臺階向上?3 個臺階，此時?到i 臺階的?案就是dp[i - 3] ；
   綜上所述，dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3] 。
3. 初始化：
   填i位置的值時，?少需要前三個位置的值，因此需要初始化dp[0] = 1, dp[1] = 1, dp[2] = 2，然后從i = 3開始填。
   或者初始化dp[1] = 1, dp[2] = 2, dp[3] = 4，然后從i = 4 開始填。
4. 填表順序：
   明顯是從左往右

#include <bits/stdc++.h>
using namespace std;typedef long long LL;const int N = 65;int n;
LL f[N]; //f[i]表示有i個臺階的時候，一共有多少種方案int main()
{ios::sync_with_stdio(false);cin.tie(0);cin >> n;//初始化f[0] = 1; f[1] = 1; f[2] = 2;for (int i = 3; i <= n; i++){f[i] = f[i - 1] + f[i - 2] + f[i - 3];       }cout << f[n] << endl;return 0;
}

動態規劃的空間優化：
我們發現，在填寫dp[i]的值時，我們僅僅需要前三個格?的值，第i-4個及其之前的格?的值已經毫??處了。因此，可以?三個變量記錄i位置之前三個格?的值，然后在填完i位置的值之
后，滾動向后更新

#include <bits/stdc++.h>
using namespace std;typedef long long LL;const int N = 65;int n;int main()
{ios::sync_with_stdio(false);cin.tie(0);cin >> n;LL a = 1, b = 1, c = 2;for (int i = 3; i <= n; i++){LL t = a + b + c;a = b;b = c;c = t;}if (n == 1) cout << b << endl;else cout << c << endl;return 0;
}

學習動態規劃最經典的??題。
解法：動態規劃

1. 狀態表?：
   dp[i][j] 表?：?到[i, j] 位置的最?權值。
   那最終結果就是在dp 表的第n ?中，所有元素的最?值。
2. 狀態轉移?程：
   根據最后?步劃分問題，?到[i, j] 位置的?式有兩種：
   a. 從[i - 1, j] 位置向下??格，此時?到[i, j] 位置的最?權值就是dp[i - 1][j] ；
   b. 從[i - 1, j - 1]位置向右下??格，此時?到[i, j] 位置的最?權值就是dp[i - 1][j - 1] ；
   綜上所述，應該是兩種情況的最?值再加上[i,j]位置的權值：
   dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1]) + a[i][j]
3. 初始化：
   因為dp 表被0 包圍著，并不影響我們的最終結果，因此可以直接填表。
   思考，如果權值出現負數的話，需不需要初始化？
   ? 此時可以全都初始化為$?\infty$ ，負?窮?在取max 之后，并不影響最終結果。
4. 填表順序：
   從左往右填寫每??，每??從左往右

#include <bits/stdc++.h>
using namespace std;const int N = 1010;int n;
int a[N][N];
int f[N][N]; //f[i][j]表示從1，1走到i，j的時候，所有方案數的最大權值int main()
{ios::sync_with_stdio(false);cin.tie(0);cin >> n;for (int i = 1; i <= n; i++)for (int j = 1; j <= i; j++)cin >> a[i][j];for (int i = 1; i <= n; i++){for (int j = 1; j <= i; j++){f[i][j] = max(f[i-1][j], f[i-1][j-1]) + a[i][j];    }}int ret = 0;for (int j = 1; j <= n; j++){ret = max(ret, f[n][j]);        }cout << ret << endl;return 0;
}

動態規劃的空間優化：
我們發現，在填寫第i ?的值時，我們僅僅需要前??的值，并不需要第i - 2 以及之前?的值。
因此，我們可以只??個?維數組來記錄上??的結果，然后在這個數組上更新當前?的值

需要注意，當?因為我們當前這個位置的值需要左上?位置的值，因此滾動數組優化的時候，要改變第?維的遍歷順序

#include <bits/stdc++.h>
using namespace std;const int N = 1010;int n;
int a[N][N];
int f[N]; //f[i][j]表示從1，1走到i，j的時候，所有方案數的最大權值int main()
{ios::sync_with_stdio(false);cin.tie(0);cin >> n;for (int i = 1; i <= n; i++)for (int j = 1; j <= i; j++)cin >> a[i][j];for (int i = 1; i <= n; i++){for (int j = i; j >= 1; j--){f[j] = max(f[j], f[j-1]) + a[i][j];    }}int ret = 0;for (int j = 1; j <= n; j++){ret = max(ret, f[j]);        }cout << ret << endl;return 0;
}