# 2023/02/12 mock interview Candidate: 阿呀呀
###### tags: `Tag(mock interview)`
---

<font size= 4><center> **倒數計時** </center></font>
<iframe id="oak-embed" width="700" height="400" style="display: block; margin: 0px auto; border: 0px;" src="http://zbryikt.github.io/quick-timer"></iframe>

# 題目講解
//time: 20:31
//end: 20:36 (louis), 20:40

length = n, m tokens

each get
v
A ai ... tokens
B bi ... get bi coins pay bi tokens

tokens we hold can't greater than m
finally find the maximum coins

5 10
5 6 0 10 2 tokens
2 3 10 0 3 coins

0 tokens
5 6 -> 10 + 3

coins = 10

// 0 token
1) 1th get 5 tokens
2) 2th get 6 tokens => tokens = 11 > 10 (greater than m tokens) keep m tokens
pay 3 tokens, can get 3 coins
4) 3th day, get 10 coins, current tokens is 0, get 10 coins
6) pay 3 token to get 3 coins, current token is 10 - 3 => 7

ans = 13 (coins)

two array A, B , and int
go through

A[i]: tokens
B[i]: coins

for each day, we can get tokens or pay tokens to get coins.

# 作法講解
// time: 20:43

if current tokens bigger than m tokens,
we must change token to coins.

5 10
5 6 0 10 2 tokens
2 3 10 0 3 coins

1: 5 token
2: case 1: 5 + 6 > 10,

case 2: 3 token to get 3 coin

3: 10 token => 10 coins

for each day, we can get more tokens,
v
5 6 0 10 2 tokens
2 3 10 0 3 coins

day 2: 3 coins, 2 token
day 3: 5 coins

v v v
5 [6] 0 10 2 tokens
2 [3] 0 0 0 coins

how we can get maximum coins

5 6 0 10 2 tokens
2 3 10 0 3 coins

day 1: 5 token
day 2: 11 token -> 10 token
day 3:
5 6 0
2 3 10
we can't get any tokens, but we can change 10 coins

maximum count of change is length of array (len - 1).

10 0 0 0 0 0 tokens
2 1 1 1 1 1 coins

dp[i][j] = x
i = token, j = coins
f
v
| {x x x} x x |
| y
first: get token, dp[last_toke + x][last_coins] = dp[last_toke][last_coins]

second: change token, dp[last_token - y][last_coins + y] = dp[last_token][last_coins]

define: dp[i] = x, i means count of tokens, x means coins,
first: get token, dp[last_token + x] = dp[last_token];

second: change token, dp[last_token - y] = dp[last_token] + y;

TC: O(n * max(token)) SC: O(max(token))

# coding
//time:

# 完成
//time: 21:03

# comment
這場花太長時間在描述題目Ｑ
不過整體來說想法上一開始小歪，不過最後還是有想到正確解法

把句子說完整, 可以說得慢一點.

# Temp

5 6 0 10 2 tokens
2 3 10 0 3 coins

// each day,
// we just try to do either first or second
// operation

// maximum coins we can get
// starting from index i, current we hold x tokens
// Func(int i, int x)

// final ans = Func(0, 0); // starting from index 0, and current token 0

// operation 1: obtain ai tokens
// Func(int i, int x) -> Func(i+1, x+ai)

// operation 2: pay bi tokens to get bi coins
// Func(int i, int x) -> bi + Func(i+1, x-bi)

// recurrence
// TC: O(2^N) -> no memoration
Func(i, x) = max(Func(i+1, x+ai), bi+Func(i+1, x-bi))

// TC: O(NX)
// top-down dp -> recursive function + memo

// record the ans in each function in a hashtable (array)

// dp[i][x]
Func(i, x) = max(Func(i+1, min(x+ai, m)), bi+Func(i+1, x-bi))

// all function will calculate only once

i=0 -> 0,1,2,3,...m
i=1 -> ...
...
i=n
Func(i, x): O(n*m) -> product each parameter range
    if (i == n) return 0;
    if (dp[i][x] != -1) return dp[i][x]; // calculate
    
    // operation1
    dp[i][x] = Func(i+1, min(x+ai, m));
    
    // operation2
    if (x >= bi)
        dp[i][x] = max(dp[i][x], bi+Func(i+1, x-bi)));
    return dp[i][x];

// dp[n], O(n)
// O(n * 1)
F(int n): possible F() n個
// O(m)
if (n == 1 || n == 2) return 1;
if (dp[n] > 1) return dp[n];
dp[n] = F(n-1)+F(n-2);
return dp[n];