C言語のコードを再帰からメモ化にしたい

[ワニ]

とあるonline judgeの問題を書きました。時間計算量が大きいためtime exceedと表示されます。時間計算量を削減するため、メモ化にしたいのです。
以下は、再帰で実装したcodeで、メモ化したいcodeです。


[code]#include <stdio.h> // scanf, printf
#include <string.h> // memset, memchr

int max(int a, int b) { return a > b ? a : b; }

int knapsack(int w, int a[], int b[], int n, char t[])
{
if (--n < 0) return w;
int len = b[n] - a[n];
if (memchr(t + a[n], 1, len)) return knapsack(w, a, b, n, t);
memset(t + a[n], 1, len);
int k = knapsack(w + len, a, b, n, t);
memset(t + a[n], 0, len);
return max(k, knapsack(w, a, b, n, t));
}



int main(void)
{
int number_of_client, max = 0, start, end;

scanf("%d", &number_of_client);

int jobs_start[number_of_client], jobs_end[number_of_client];

for (int i = 0; i < number_of_client; i++) {
scanf("%d%d", &jobs_start[i], &jobs_end[i]);
if (jobs_end[i] > max) max = jobs_end[i];
}

scanf("%d%d", &start, &end);
if (end > max) max = end;
char t[max];
memset(t, 1, max);//tを初期化
memset(t + start, 0, end - start);
printf("%d\n", knapsack(0, jobs_start, jobs_end, number_of_client, t));
}
[/code]

Description：
現在、サスケは複数のクライアントから依頼を受け取っており、各依頼にはクライアントが指定した開始日と完了日があります（必要な稼働日数は完了日から開始日を引いたものです）サスケはどの注文を約束するかを知りませんでした。
複数のクライアントによって指定された開始日と完了日、およびサスケの作業の開始日と終了日を知っているので、サスケが最大の収入を得ることができるように、サスケがクライアントの依頼を選択するのを手伝ってください。
たとえば、サスケは7つのクライアントの依頼を受け取り、指定された日付と完了日は{[6、10]、[10,12]、[8,13]、[3,7]、[1,6]、[13 、16]、[5、9]}、サスケが{[1,6]、[6,10]、[10,12]、[13,16]を選択した場合、サスケは1日目から16日目まで動作することが知られています。 ]}これら4人の顧客の手数料であるサスケの収入が最も多く、合計で5 + 4 + 2 + 3=14日間の収入があります。マリオが3日目から12日目まで働く場合は、{[3,7]、[10,12]}または{[5、9]、[10、12]}または{[6、10]、[10、12 ]}手数料、マリオが最も収入があり、合計4 + 2=6日間の収入です。
sample input
7
6 10
10 12
8 13
3 7
1 6
13 16
5 9
1 16

sample output
14

[みけCAT]

ソースコードを提示する際は、BBCodeが有効な(無効にしない)状態で、
BBCodeのcodeタグの開始タグと終了タグの組(開始タグが先)で囲んでいただけると、
見やすくてありがたいです。

とあるonline judgeの問題を書きました。

制約が知りたいですが、問題文の一部でググってもここしか出なそうでわかりませんね…
C言語で動的計画法（ナップサック問題）を用いて最大出勤日を出す
(約1年前の質問で、コードも違うので、マルチポストではないでしょう)

時間計算量を削減するため、メモ化にしたいのです。

すればいいのではないでしょうか？
質問はありますか？

[ワニ]

[/nfo]

とあるonline judgeの問題を書きました。時間計算量が大きいためtime exceedと表示されます。時間計算量を削減するため、メモ化にしたいのです。
以下は、再帰で実装したcodeで、メモ化したいcodeです。

コード:

#include <stdio.h>   // scanf, printf
#include <string.h>  // memset, memchr

int max(int a, int b) { return a > b ? a : b; }
  
int knapsack(int w, int a[], int b[], int n, char t[])
{
	if (--n < 0) return w;
	int len = b[n] - a[n];
	if (memchr(t + a[n], 1, len)) return knapsack(w, a, b, n, t);
	memset(t + a[n], 1, len);
	int k = knapsack(w + len, a, b, n, t);
	memset(t + a[n], 0, len);
	return max(k, knapsack(w, a, b, n, t));
}



int main(void)
{
	int number_of_client, max = 0, start, end;
	
	scanf("%d", &number_of_client);
	
	int jobs_start[number_of_client], jobs_end[number_of_client];
	
	for (int i = 0; i < number_of_client; i++) {
		scanf("%d%d", &jobs_start[i], &jobs_end[i]);
		if (jobs_end[i] > max) max = jobs_end[i];
	}
	
	scanf("%d%d", &start, &end);
	if (end > max) max = end;
	char t[max];
	memset(t, 1, max);//tを初期化
	memset(t + start, 0, end - start);
	printf("%d\n", knapsack(0, jobs_start, jobs_end, number_of_client, t));
}

Description：
現在、サスケは複数のクライアントから依頼を受け取っており、各依頼にはクライアントが指定した開始日と完了日があります（必要な稼働日数は完了日から開始日を引いたものです）サスケはどの注文を約束するかを知りませんでした。
複数のクライアントによって指定された開始日と完了日、およびサスケの作業の開始日と終了日を知っているので、サスケが最大の収入を得ることができるように、サスケがクライアントの依頼を選択するのを手伝ってください。
たとえば、サスケは7つのクライアントの依頼を受け取り、指定された日付と完了日は{[6、10]、[10,12]、[8,13]、[3,7]、[1,6]、[13 、16]、[5、9]}、サスケが{[1,6]、[6,10]、[10,12]、[13,16]を選択した場合、サスケは1日目から16日目まで動作することが知られています。 ]}これら4人の顧客の手数料であるサスケの収入が最も多く、合計で5 + 4 + 2 + 3=14日間の収入があります。マリオが3日目から12日目まで働く場合は、{[3,7]、[10,12]}または{[5、9]、[10、12]}または{[6、10]、[10、12 ]}手数料、マリオが最も収入があり、合計4 + 2=6日間の収入です。
sample input
7
6 10
10 12
8 13
3 7
1 6
13 16
5 9
1 16

sample output
14

[usao]

https://teratail.com/questions/nfa2qzxqqvlmup