[TIOJ] 1007燈泡問題

題目連結：http://tioj.ck.tp.edu.tw/problems/1007

我不會DP QAQ
　　這題我很久以前就寫過了，因為想起來OTOTOT說過的必須要複習學過的東西，所以最近想要將TIOJ裡的我寫過的題目都再刷過一次。
　　　由第 i 個燈泡開始亮0~n個後再接一個暗的，容易可以推出DP式：dp[ i ] = dp[ i-1 ]+dp[ i-2 ]+...+dp[ i-n-1 ] ，複雜度是O(NM)，雖然夠了但其實可以化簡，可以發現dp[ i ]-dp[ i-1 ]=dp[ i-1 ]-dp[ i-n-2 ]，也就是說dp[ i ] = 2*dp[ i-1 ]-dp[ i-n-2 ]，複雜度降到了O(M)。
　　不過在i <n+2時要注意（我數學不好@@，這裡一直搞混），i<=n時可以隨意開關所以是2^n，而 i=n+1 時根據原本的DP式可以知道式所有前面的項相加其實也就是2*(n+1)-1，而後面的直接DP即可

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m;
int dp[100];
main()
{
    cin >> n >> m;
    dp[0] = 1;
    for(int i = 1; i <= n; i++)
         dp[i] = dp[i-1]<<1;
    dp[n+1] = (dp[n]<<1)-1;
    for(int i = n+2; i <= m; i++)
        dp[i] = (dp[i-1]<<1)-dp[i-n-2];
    cout << dp[m] << endl;
}