1003 . 切義大利餅問題

題目連結: https://tioj.ck.tp.edu.tw/problems/1003

# 內容

電腦程式語言的架構中，遞迴函數可說是較特殊的一種，因函數可以呼叫函數本身自己。

請設計一個程式，用遞迴函數解決下面兩小題 (Problem 1003, Problem 1004)。

設有一 16 吋義大利脆餅，今欲以刀切餅，每刀均以直線方式切於餅面，第一刀可將脆餅切成兩片，二刀至多可分成 4 片，三刀至多可分成 7 片，試問$n$ 刀至多可將脆餅切成幾片？令$f(n)$ 為$n$ 刀將脆餅分成的片數，則$f(0)=1$。

# 思路

切零刀最多能有 1 片
切一刀最多能有 2 片
切二刀最多能有 4 片
切三刀最多能有 7 片
切四刀最多能有 11 片
.................
-> $f(n) = 1,if(n=0)$
-> $f(n) = f(n-1)+n$

# 程式碼

#include <iostream>

#define int long long

using namespace std;

main()

{

    int dp[51]={};

    dp[0] = 1;

    int n;

    cin>>n;

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

        dp[i] = dp[i-1]+i;

    cout<<dp[n]<<endl;

}