Uva11420 | Chest Of Drawers | YHC2538 = 生活 x 程式筆記 = 努力向上

第一篇筆記～

Difficulty:

⭐️⭐️

# Problem Description 題敘:

Link

給你一個櫃子，上到下共 $n$ 層抽屜，每層可以選擇要上鎖與否，請問讓 $s$ 個櫃子是安全的有幾種方法呢？

不安全的定義：這層未上鎖 or 上面那層沒上鎖。

兩個整數 $n$ 及 $s$ ， $(1 ≤ n ≤ 65,\ 0 ≤ s ≤ 65)$ 。其中 n 是共有幾層抽屜，s 是要確保安全的抽屜數量。

# Thinking 思考歷程:

此問題是資芽的 $dp$ 例題，因此就直接往 $dp$ 的方想來想。題目告訴我說，每層可選擇上鎖與否，那我能想到說這題一定跟鎖與不鎖之間分成兩類。剛開始，我試了想用二維 $dp$ 去解它，所以定義了 $dp[i][j]$ ，即有 $i$ 層，讓 $j$ 個櫃子是安全的方法數，且讓最後一層 $i$ 有鎖。但這當然很快在寫轉移式的時候就遇到瓶頸了，因為很難用只用 $i$ 這個變數，紀錄層數和紀錄鎖與不鎖。那這很顯然就是錯的，於是我看了一部分的題解，發現要設三個狀態 $k$ ，紀錄鎖的情形，就能比較容易寫出式子之間的關聯。最後就能推出來式子了。

# Solution 題解:

此問題屬於計數 $dp$ 。網路上有查到兩種做法，一種主要是從櫃子的最上層，一直做到櫃子的最下層；另一種則反之。

我們先定義 dp[i][j][k] = [由上往下數第 i 層][確定了有j個抽屜是安全的][鎖與不鎖] 。最後的一層抽屜 "鎖與不鎖" 也包含再 $j$ 個裡面。

# 第 1-1 種作法:

第一種解法就是從上面做到下面。在這裡先示範用 "推" 的概念，並以上面那層 (第 $i$ 層) 為基準，考慮第 $i+1$ 層。 (也可暫且把 $i+1$ 層當作最後一層)

如果這層 ( $i+1$ ) 確定的抽屜安全數量是 $j+1$ 的話 (也就是比上面那層多 $1$ 個)，只有一類:
dp[i+1][j+1][1] += dp[i][j][1]
那就會導致我這層一定鎖，並且我的上面那層也一定有鎖。因此方法數加上上層要鎖的數量。
如果這層 ( $i+1$ ) 確定的抽屜安全數量是 $j$ 的話 (也就是跟上面那層相同)，可以分為兩類:
- 如果這層要鎖:
  dp[i+1][j][1] += dp[i+1][j][0]
  那我上面那層就不能鎖，否則 $j$ 會加 $1$ 而跟我們上面那種分類重疊。因此方法數加上上層不鎖的數量。
- 如果這層不鎖:
  dp[i+1][j][0] += dp[i][j][0] + dp[i][j][1]
  那代表這層對抽屜安全的數量沒有影響，因此方法數加上上層鎖與不鎖的數量。

初始條件:

由於 $n \geq 1,\ s \geq 0$ ，因此 dp[1][0][0] = dp[1][1][1] = 1 ，如果只有一層，又有 $0$ 個櫃子是安全的，那我最後一個抽屜鐵定不能鎖，方法數 $1$ 種；換成有一個抽屜是安全的，那最後一層就要鎖了，方法數也是只有 $1$ 種。

最後的答案:

根據我們的定義 $dp[i][j][k]$ 的定義， $dp[n][s][1] + dp[n][s][0]$ 即為答案，也就是最後一層鎖與不鎖的方法數和。

到這邊，我曾思考為甚麼這個轉移要用 += 而非 = 呢？其實理由很簡單，因為有可能不只一種狀態會轉移到它。

以 dp[2][1][1] 為例子 (詳細請看 Code 1):

假設 i = 1, j = 0，

會計算 dp[1+1][0+1][1] (dp[2][1][1]，被計算到第一次) += dp[1][0][1]
會計算 dp[1+1][0][0] (dp[2][0][0]) += dp[1][0][0] + dp[1][0][1]
會計算 dp[1+1][0][1] (dp[2][0][1]) += dp[1][0][0]

之後到了 i = 1, j = 1，

會計算 dp[1+1][1+1][1](dp[2][2][1]) += dp[1][1][1]
會計算 dp[1+1][1+0][0](dp[2][1][0]) += dp[1][1][0] + dp[1][1][1]
會計算 dp[1+1][1+0][1](dp[2][1][1]，被計算到第二次) += dp[1][1][0]

如此就可以發現，如果用 = 的話，先前的值就會被覆蓋過去，因此如果用 "推" 的話，再滿多情況都要用 += 的。

###　第 1-2 種做法:

這種解法要示範同樣由上到下，但換成用 "拉" 的。那我個人是認為用拉的比較直覺，而且遞迴式更好想。我們可以就讓鎖與不鎖分兩類:

dp[i][j][0] = dp[i-1][j][1] + dp[i-1][j][0]

dp[i][j][1] = dp[i-1][j-1][1] + dp[i-1][j][0]

需要注意的地方， $j$ 一定要從 $0$ 開始算，否則會少掉 $j = 0$ 的一些解，因此，如果不做特別處理的話，第二行的遞迴式的 $j-1$ 有可能出現負的，因此還是要加一點特判才行。Code 在底下 (1-2)。

# 第 2 種做法:

既然有從上到下那就會有從下到上，一路疊上去的做法囉。這裡就只示範用 "推" 的寫法。

我們的以下面一層為基準 (第 $i$ 層)，考慮目前的第 $i+1$ 層，由於我這層會影響下面一層的目前安全抽屜數量，因此:

假設目前這層是最上面那層，那如果我這層有鎖，那我的抽屜安全數量，就會比我下面那層多一。(因為不會有再更上面一層了)
那其實這層的法數就是從我下面一層鎖或不鎖轉過來的。
dp[i+1][j+1][1] = dp[i][j][1] + dp[i][j][0]
反之如果我沒有鎖當前這層，那我下面那層的安全數量就要減一。 (因為之前我們算下面一層的時候，暫且把它當作了最上面那層)
那我下面一層可能是有鎖，且安全數量多一的情況轉移過來的；或者是那層沒鎖。(舉例來說：連續沒鎖的情況)
dp[i+1][j][0] = dp[i][j+1][1] + dp[i][j][0]

這個做法我也很喜歡，因為如果用 "推" 的就不用處理負數或其他特殊情況，因此這種寫法是很乾淨的。

# AC Code 程式碼:

# Code 1-1. 上到下，用 "推" 的作法:

	#include <bits/stdc++.h>
	typedef long long LL;
	const int N = 1e2;
	LL dp[N][N][2];
	int main(){
	IOS; int n,s;
	dp[1][0][0] = dp[1][1][1] = 1;
	for(int i = 1; i < 70; i++){
	for(int j = 0; j <= i; j++){
	dp[i+1][j+1][1] += dp[i][j][1];
	dp[i+1][j][1] += dp[i][j][0];
	dp[i+1][j][0] += dp[i][j][0] + dp[i][j][1];
	}
	}
	while(cin>>n>>s, n>0){
	cout<<(dp[n][s][0] + dp[n][s][1])<<'\n';
	}
	}

# Code 1-2 上到下，用 "拉" 的作法:

	#include <bits/stdc++.h>
	typedef long long LL;
	const int N = 1e2;
	LL dp[N][N][2] = {};
	int main(){
	IOS; int n,s;
	dp[1][0][0] = dp[1][1][1] = 1;
	for(int i = 2; i <= 70; i++){
	for(int j = 0; j <= 70; j++){
	dp[i][j][1] = (j>0 ? dp[i-1][j-1][1] : 0) + dp[i-1][j][0];
	dp[i][j][0] = dp[i-1][j][1] + dp[i-1][j][0];
	}
	}
	while(cin>>n>>s, n > 0){
	cout<<(dp[n][s][1] + dp[n][s][0])<<'\n';
	}
	}

# Code 2 下到上，用推的:

	#include <bits/stdc++.h>
	typedef long long LL;
	using namespace std;
	const int N = 1e2;
	LL dp[N][N][2] = {};
	int main(){
	int n,s;
	dp[1][0][0] = dp[1][1][1] = 1;
	for(int i = 1; i <= 70; i++){
	for(int j = 0; j <= i; j++){
	dp[i+1][j+1][1] = dp[i][j][1] + dp[i][j][0];
	dp[i+1][j][0] = dp[i][j+1][1] + dp[i][j][0];
	}
	}
	while(cin>>n>>s, n > 0){
	cout<<(dp[n][s][1] + dp[n][s][0])<<'\n';
	}
	}

<br/>

# 學習到的新技巧和概念～

做 $dp$ 時，當發現定義的內容不夠詳細，造成轉移很難推倒時，可以試試再增加一個維度。
在側資較小時可以先全部算完可能的情形再根據提問再輸出。
若是計數 $dp$ ，如果用 "推" 的，基本上都是用 += (因為同一個狀態的前置狀態們的順序可能有先後，如果用 = ，可能會覆蓋掉前個值) 。
只要轉移式跟計算順序是合理的，那其實用推的、拉的、由下而上或由上而下都可以耶。