象棋问题
递归版本
现在给你一个横长为10 纵长为9的棋盘 给你三个参数 x y z
现在一个马从（0 , 0）位置开始运动
提问 有多少种方法使用K步到指定位置 （指定位置坐标随机给出 且一定在棋盘上）
首先我们可以想出这么一个函数
int process(int x , int y , int rest , int a , int b)
它象棋目前在 x y位置 还剩下 rest步 目的地是到 a b位置
让你返回一个最多的路数
我们首先来想base case
- 首先肯定是剩余步数为0 我们要开始判断是否跳到目的地了
- 其次我们还要判断是否越界 如果越界我们直接返回0即可
代码表示如下
if (x < 0 || x > 9 || y < 0 || y > 8) { return 0; } if (rest == 0) { return (x == a && y ==b) ? 1 : 0; }
接下来我们开始讨论普遍情况 其实就是把马的各个位置跳一遍
int ways = process(x-2 , y+1 , rest-1 , a , b); ways += process(x-1 , y+2 , rest-1 , a , b); ways += process(x+1 , y+2 , rest-1 , a , b); ways += process(x+2 , y+1 , rest-1 , a , b); ways += process(x-2 , y-1 , rest-1 , a, b); ways += process(x-1 , y-2 , rest-1 , a , b); ways += process(x+1 , y-2 , rest-1 , a, b); ways += process(x+2 , y-1 , rest-1 , a ,b);
其实这样子我们的代码就完成了 总体代码如下
int process(int x , int y , int rest , int a , int b) { if (x < 0 || x > 9 || y < 0 || y > 8) { return 0; } if (rest == 0) { return (x == a && y ==b) ? 1 : 0; } int ways = process(x-2 , y+1 , rest-1 , a , b); ways += process(x-1 , y+2 , rest-1 , a , b); ways += process(x+1 , y+2 , rest-1 , a , b); ways += process(x+2 , y+1 , rest-1 , a , b); ways += process(x-2 , y-1 , rest-1 , a, b); ways += process(x-1 , y-2 , rest-1 , a , b); ways += process(x+1 , y-2 , rest-1 , a, b); ways += process(x+2 , y-1 , rest-1 , a ,b); return ways; }
动态规划
我们对于原递归函数进行观察 可以得知
int process(int x , int y , int rest , int a , int b)
原函数中 变化的参数只有 x y 和rest 于是乎我们可以建立一个三维的数组
x的范围是0 ~ 9 y的范围是0 ~ 8 而rest的范围则是根据我们步数来决定的 0~K
所以说此时我们以X为横坐标 Y为纵坐标 REST为竖坐标
vector<vector<vector<int>>> dp(10 , vector<vector<int>>(9 , vector<int>(8 , 0)));
我们首先看base case分析下
if (x < 0 || x > 9 || y < 0 || y > 8) { return 0; }
如果有越界的地方 我们直接返回0即可
if (rest == 0) { return (x == a && y ==b) ? 1 : 0; }
在z轴为0的时候 我们只需要将a b 0坐标标记为1即可
nt process1(int k , int a , int b , vector<vector<vector<int>>>& dp) { dp[a][b][0] = 1; for (int z = 1; z <= k; z++) { for (int x = 0; x < 10; x++) { for (int y = 0; y < 9; y++) { int ways = pickdp(x-2 , y+1 , z-1, dp); ways += pickdp(x-1 , y+2 , z-1 , dp); ways += pickdp(x+1 , y+2 , z-1 , dp); ways += pickdp(x+2 , y+1 , z-1 , dp); ways += pickdp(x-2 , y-1 , z-1 , dp); ways += pickdp(x-1 , y-2 , z-1 , dp); ways += pickdp(x+1 , y-2 , z-1 , dp); ways += pickdp(x+2 , y-1 , z-1 , dp); dp[x][y][z] = ways; } } } return dp[0][0][k]; }
咖啡机问题
给你一个数组arr arr[i]表示第i号咖啡机泡一杯咖啡德时间
给定一个正数N 表示第N个人等着咖啡机泡咖啡 每台咖啡机只能轮流泡咖啡
只有一台洗咖啡机 一次只能洗一个被子 时间耗费a 洗完才能洗下一杯
当然 每个咖啡杯也能自己挥发干净 挥发干净的时间为b 咖啡机可以并行的挥发
假设所有人拿到咖啡之后立刻喝干净
返回从开始等待到所有咖啡机变干净的最短时间
我们首先来分析下题目
这里其实是两个问题
- 问题一 每个人喝咖啡喝完的时间是多少
- 问题二 每个人洗完的时间是多少
对于问题一 我们可以使用一个小根堆来做
我们定义一个机器类 里面有两个成员函数
机器的开始时间和机器的使用时间 我们使用它们相加之和来作为小根堆排序的依据
之后我们就能得到每个人喝完咖啡的最优解了
class Machine { public: int _starttime; int _worktime; public: int getsum() const { return _starttime + _worktime; } public: Machine() = default; Machine(int st , int wt) :_starttime(st) ,_worktime(wt) {} bool operator()(const Machine& obj1 , const Machine& obj2) { return obj1.getsum() > obj2.getsum(); } };
vector<int> process(vector<int>& arr , int num) { vector<int> ans; priority_queue<Machine , vector<Machine> , Machine> heap; for (auto x : arr) { heap.push(Machine(0 , x)); } for (int i = 0; i < num; i++) { Machine cur = heap.top(); heap.pop(); ans.push_back(cur.getsum()); cur._starttime += cur._worktime; heap.push(Machine(cur._starttime , cur._worktime)); } return ans; }
递归版本
我们在写递归版本的时候首先要想到递归函数的含义
它的含义是返回一个所有咖啡杯都被洗完的最小值
之后我们可以想base case 当什么样的时候 该函数无法递归了
最后列出所有可能性即可
int process(vector<int>& end , int index , int a , int b , int avltime) { if (index == static_cast<int>(end.size())) { return 0; } // possible 1 int p1 = max(a + end[index] , process(end , index+1 , a , b , avltime)); // possible 2 int p2 = max(b + end[index], process(end , index+1 , a , b , avltime + b)); return min(p1 , p2); }
动态规划
这个问题的动态规划涉及到一个大小问题
因为我们无法确定avltime使用到的时间 所以这里有两种解决方案
- 将它开辟的足够大
- 根据最大值计算 （假设所有人都用咖啡机洗）
int dpprocess(vector<int>& end , int a , int b , vector<vector<int>> dp) { // dp[N][...] = 0; for (int indexdp = static_cast<int>(end.size()) - 1; indexdp >= 0 ; indexdp--) { for (int freetime = 0; freetime <= 10000 ; freetime++) { int p1 = max(a + end[indexdp] , dp[indexdp+1][freetime]); int p2 = max(b + end[indexdp] , dp[indexdp+1][freetime+b]); dp[indexdp][freetime] = min(p1 , p2); } } return dp[0][0]; }
