TIOJ 1007 燈泡問題

　　這題幾天前就ＡＣ了,但是今天回去看了我的code,發現我根本不知道我在寫什麼ＱＱ

所以我以後打算稍微記下來,不然忘記很痛苦欸,還讓我去看日劇放鬆一下

　　這題很明顯就是ＤＰ,由於數字範圍不大,開個二維陣列不是問題,所以直接開始想狀態和轉移方程

我的想法就很簡單,如果當前要求時間長度為k的答案（最長持續亮時間仍是n),

可以分開討論

1,最後一格是暗的＝＞條件為＂時間長度為k-1"（最長持續亮時間是n)

2,最後一格是亮的＝＞條件為＂時間長度為k-1　且　末端的最長持續亮時間是n-1＂

那麼來定義狀態

dp[x][y]是指　時間長度為x ,而末端的最長持續亮時間是y

轉移方程就會變成

dp[x][y]=dp[x-1][n]+dp[x-1][y-1];

而dp[x][0]就是dp[x-1][n];

而邊界條件呢？

dp[1][0]=1 由於末端不能亮（最長持續亮時間是0) 所以只能是暗的

dp[1][y]=2 for 1<=y<=n 亮或不亮皆可

這樣就解決了這題　時間複雜度是Ｏ(mn) 空間複雜度也是Ｏ(mn) 

可是是說空間好像可以壓縮欸,每次轉移都只有用到上一列的狀態

所以可以把列數省略掉　dp[m][n]變成　dp[n] 而空間變成Ｏ(n)

這樣　就有以下的code

#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ll;
ll n,m;
ll dp[16];
int main(){
cin>>n>>m;
dp[0]=1;
for(int i=1;i<=n;i++){
dp[i]=2;
}
for(int i=2;i<=m;i++){
ll x=dp[n];
for(int j=n;j>0;j--){
dp[j]=x+dp[j-1];
}
dp[0]=x;
}
cout<<dp[n]<<'\n';
}