我们可以一句话总结下动态规划
动态规划本质是一种以空间换时间的行为 如果你发现有重复调用的过程 在经过一次之后把结果记下来 下次调用的时候直接用 这就是动态规划
斐波那契数列的动态规划
一般来说我们可以使用递归来解决斐波那契数列问题 代码如下
int fib(int n) { if (n <= 0) { cerr << "error" << endl; } if (n <= 2) { return 1; } return fib(n-1) + fib(n-2); }
当然 这种方式会产生大量的重复计算 所以说我们可以保存上个和上上个的计算值来进行动态规划
int dpfib(int n) { if (n <= 2) { return 1; } int i = 1; int j = 1; int k = 0; while (n-2) { k = i + j; i = j; j = k; n--; } return k; }
这样子写代码就能避免大量的重复计算了
机器人走路
初级递归
假设现在有1~N个位置
有一个小机器人 现在在START位置
它现在要去aim位置 （aim为1~N上的随机一点） 能走K步 （K >= 0）
每次只能走一步 不能越界 不能停止 现在请问有多少种方式能走走到
现在假设 S = 2 N = 5 AIM = 4 K = 6
我们一开始写出的递归方程如下
int process1(int cur , int rest , int aim , int k)
参数含义如下
- cur 当前位置
- rest 剩余步数
- aim 目标地点
- k 能走的步数
base case为
- 如果剩余步数为0 则判断cur是否为aim地点
否则我们执行递归继续往下走
int process1(int cur , int rest , int aim , int n) { if (rest == 0) { return cur == aim ? 1 : 0; } if (cur == 1) { return process1(2 , rest -1 , aim , n); } if (cur == n) { return process1(n-1 , rest-1 , aim , n); } return process1(cur-1 , rest-1 , aim , n) + process1(cur+1 , rest-1 , aim , n); }
初级动态规划
现在我们要进行进一步的动态规划
我们想想看在递归函数中有真正决定的是哪两个参数
我们每次传递参数的时候 aim 和 n 是不变的
其实每次变化的就是 cur 和 rest
我们可以将该函数往下推演 我们会发现会出现两个相同的结果
如果继续往下展开的话则肯定会有重复的部分 所以说我们最好能将这些函数的结果记录下来 避免重复计算
我们选择使用一个二维数组存储每个函数的计算结果
vector<vector<int>> dp(n + 1 , vector<int>(rest + 1)); for (int i = 0 ; i < n + 1 ; i++ ) { for (int j = 0; j < rest + 1 ; j++) { dp[i][j] = -1; } }
这个二维数组 i j 分别标识当前位置和剩余步数
该数组的值表示在当前位置下走剩余步数能走到目的地有多少种解法
我们首先全部初始化为-1
int _process2(int cur , int rest , int aim , int n , vector<vector<int>>& dp) { if (dp[cur][rest] != -1) { return dp[cur][rest]; } int ans = 0; if (rest == 0) { ans = cur == aim ? 1 : 0; } else if (cur == 1) { ans = _process2(2 , rest-1 , aim , n , dp); } else if (cur == n) { ans = _process2(n-1 , rest-1 , aim , n , dp); } else { ans = _process2(cur -1 , rest -1 , aim , n , dp ) + _process2(cur +1 , rest -1 , aim , n , dp); } dp[cur][rest] = ans; return ans; }
之后在我们的函数中 如果数组中有结果 我们就直接返回 如果没有结果我们就将结果记录在数组中后返回 也能得到一样的结果
动态规划
我们以cur为横坐标 rest为纵坐标画一个图 并且将cur为0的时候值填入图中
当cur为1的时候 我们回顾下我们的代码 我们会发现 此时该格上的数字只依赖于 dp[2][rest-1]
当cur为n的时候 我们回顾下之前的带啊吗 我们会发现 此时该格上的数字只依赖于 dp[n-1][rest-1]
当cur介于两者之间的时候 此时该格上的数字依赖于两种路径
dp[cur-1][rest-1] + dp[cur+1][rest-1]
那么我们既然有了第一列的数字 我们就可以推出整个dp数组的数值
从而我们就能得出 当前为start 还有k步要走的时候 我们有几种路径
代码表示如下
int process3(int cur , int rest , int aim , int n) { vector<vector<int>> dp(n + 1 , vector<int>(rest + 1)); for (int i = 0 ; i < n + 1 ; i++ ) { for (int j = 0; j < rest + 1 ; j++) { dp[i][j] = 0; } } // row 1 dp[aim][0] = 1; for (int r = 1 ; r <= rest ; r++) { dp[1][r] = dp[2][r-1]; for (int c = 2 ; c < n ; c++) { dp[c][r] = dp[c-1][r-1] + dp[c+1][r-1]; } dp[n][r] = dp[n-1][r-1]; } return dp[cur][rest]; }
这就是完整的解决动态规划问题的步骤
