零钱兑换+三次握手与四次挥手

零钱兑换

题目描述：给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。
你可以认为每种硬币的数量是无限的。

来源：力扣（LeetCode）322

暴力递归：
递归dp(amount) 形参表示目标金额，想要求凑出amount至少需要多少枚硬币，就要先求凑出amount-coins[i]至少需要几枚硬币，那么就有了递归函数式：
res = min(res, dp(amount-coins[i])+1);
res表示结果，目标金额减去其中一枚硬币生成新的目标金额（amount-coins[i]）再加1表示凑出(amount-coins[i])需要的硬币个数加上当前减去的这枚硬币 就求出了最终结果。

当amount=0时就不用凑了直接返回0。
当amount-coins[i] < 0时，表示这种凑发不合理，无解。
所以递归的退出条件如下：

dp(amount){
	if(amount == 0) return 0;
	if(amount-coins[i] < 0) return -1;
}

现在有了递归函数和退出条件不难写出递归：
伪代码如下：

 int coinChange(vector<int>& coins, int amount) {
 	dp(n){
 		int res = amount+1; // 最大值
		if(n == 0) return 0;
		for(int i = 0; i < coins.size(); ++i){
			if(n - coins[i] < 0) continue; // 无解跳过
			res = min(res, dp(n-coins[i])+1);
		}
		return res == amount+1 ? -1 : res;
	}
	return dp(amount);
 }

此时的时间复杂度为O(kn^k)
暴力递归无疑会有很多的重复解，所以下一步去除重复解。
加备忘录的递归：
伪代码如下

int coinChange(vector<int>& coins, int amount) {
	vector<int> dict(amount+1, amount+1);
 	dp(n, vector<int>&){
 		int res = amount+1; // 最大值
		if(n == 0) return 0;
		if(dict[n] != amount+1) return dict[n]; // 备忘录有的直接拿来用
		for(int i = 0; i < coins.size(); ++i){
			if(n - coins[i] < 0) continue; // 无解跳过
			res = min(res, dp(n-coins[i], dict)+1);
		}
		dict[n] = res == amount+1 ? -1 : res; // 先记录到备忘录
		return dict[n];
	}
	return dp(amount, dict);
 }

此时的时间复杂度为O(kn)
上述都是自顶向下的解决方式，下面来自底向上解决，实际上上述的递归式就是一个状态转移函数。现在用循环来解决问题，无非就是将状态转移函数数组化。
动态规划数组定义：下标 i 表示目标金额，dp[i] 表示凑成目标金额的最少枚数。
转换成循环解决代码如下：

int myMin(int a, int b){
	return a < b ? a : b;
}
int coinChange(vector<int>& coins, int amount) {
        vector<int> dp(amount+1, amount+1);
        dp[0] = 0; // 目标金额为0时
        for(int i = 0; i < dp.size(); ++i){
            for (int j = 0; j < coins.size(); ++j){
                int temp = i - coins[j];
                if(temp < 0) continue;
                dp[i] = myMin(dp[i], dp[temp]+1);
            }
        }
        return dp[amount] == amount+1 ? -1 : dp[amount];
}
   

时间复杂度依然为O(kn)。

三次握手与四次挥手

直接看图一目了然。
三次握手

分析：
三次握手发生于客户端与服务端的TCP连接时期。
第一次握手： 客户端将SYN置1表示请求连接，随机生成一个seq码封装到请求报文发送给服务端请求连接。
第二次握手： 服务端收到报文，也将SYN置1表示可以连接，ACK置1表示确认收到请求报文，ack=seq+1(注意这里的seq是客户端请求连接时的随机seq)，服务端也随机生成一个seq序列号(这个seq!=客户端的seq)，服务器将以上信息封装为响应报文发送给客户端。
第三次握手： 客户端收到服务器的响应报文后，对于客户端而言已经知道了自己能发也能收，但是对服务器而言是不知道自己发送是否成功的，所以就有了第三次握手。客户端将ACK置1表示确认收到，ack=seq+1(服务器发来的seq)，将上述信息封装到报文里发送给服务器，服务端收到报文后，就知道自己能发送成功了。这时客户端与服务器端就建立了可靠的连接。

四次挥手

分析：
四次挥手发生于TCP方式的客户端与服务端断开连接的时期。
第一次挥手： 客户端将FIN置1表示断开连接请求，随机生成一个seq序列号，将其封装为报文发送给服务端。
第二次挥手： 服务器收到客户端的报文后发现FIN=1，就指定客户端要断开连接，这时服务器还有与客户端交互时的数据没有处理完成，所以服务器回一个ACK=1，ack=seq+1(客户端的seq)确认收到请求，让客户端先等一会，等我处理完再给你说。
第三次挥手： 服务器这时已经处理完了与客户端最后的交互数据，这时可以断开了，服务器将FIN置1随机生成一个seq(这个seq不同于客户端的seq)发给客户端表示现在可以断开了。
第四次挥手： 客户端收到服务器的报文后回一个ACK=1，ack=seq+1(服务器发来的seq)报文确认断开。
此时客户端与服务器就断开了连接。

延申
有没有可能三次挥手？
答案是有的，因为当客户端发来断开连接的请求时，服务器效率很高，刚好也处理好了最后的数据，这时服务器就会将第二次和第三次挥手一次性执行完。所以有三次挥手的可能。