从暴力递归到动态规划

暴力递归：

1、把问题转化为ie规模缩小了的同类问题的子问题 2、有明确的不需要继续进行递归的条件（base case） 3、有当得到了子问题结果之后的决策过程 4、不记录每一个子问题的解

例一：求n!的结果

这道题很简单，你的脑中可能会出现一个非递归版本的解法，那是我们知道它该怎么算的状况下，现在我们来看看递归版本： 递归版本的思想是：求n!,只要去求(n-1)!然后乘以n

long getFactorial(int n){ if (n==1){ return 1; } return n*getFactorial(n-1); }

例二：汉娜塔问题

打印n层汉娜塔从最左边移动道到右边的全部过程。

这道题抽象一下，就是from，to和help三个杆， 要把1到n彻底挪到to上， 第一步，是把1到n-1从from挪到help上 第二步，把n从from挪到to上 第三步，把 1到n-1从help挪到to上

下面看代码：

void process(int N, string from, string to, string help){ if(N==1){ cout<<"move 1 from "<<from<<" to "<<to<<endl; } else{ process(N-1,from,help,to); cout<<"move "<<N<<" from "<<from<<" to "<<to<<endl; process(N-1,help,to,from); } }

例三：打印一个字符串的全部子序列，包括空字符串

举例说明什么叫子序列吧： "abc"的子序列："abc","ab","ac","bc","a","b","c"," " 方法是每一0，1，2每个位值都判断是否要，穷举所有的可能

下面看代码

void printAllSub(string str, int i, const string &res) { if (i == str.size()) { cout << res << endl; return; } printAllSub(str, i + 1, res); printAllSub(str, i + 1, res + str[i]); }

例四： 打印一个字符串的全排列

void swap(string &s,int i,int j){ char temp=s[i]; s[i]=s[j]; s[j]=temp; } void printAllArray(string str,int i){ if(i==str.size()){ cout<<str<<endl; } for(int j=i;j<str.size();j++){ swap(str,i,j); printAllArray(str,i+1); } }

例五： 母牛每年生一只母牛，新出生的母牛成长三年后也能每年生一只母牛，假设不会死。求n年后，母牛的数量

小规模的自己数一下会发现，头4年牛的数量是1、2、3、4， 往后，第n年牛的数量F(n)=F(n-1)+F(n-3),然后可以想想为什么会有这样的规律，F(n)是今年的牛，F(n-1)是去年的牛，因为牛都不会死，所以去年的数量会保留，F（n-3）是三年前的牛，因为所有三年前的牛都会生新的牛

下面是代码

int process1(int n){ if(n<1){ return 0; } if(n==1||n==2||n==3) return n; return process1(n-1)+process1(n-3); }

动态规划

1、从暴力递归中来 2、将每一个子问题的解记录下来，避免重复计算 3、把暴力递归的过程，抽象成了状态表达 4、并且存在化简状态表达，使其更加简洁的可能

下面这道题，我们要展示，怎么从暴力递归，走向动态规划：

例1： 给你一个二维数组，二维数组中的每个数都是正数，要求从左上角走到右下角，每一步只能向右或者向下。沿途经过的数字要累加起来。返回最小的路径和。

事实上所有的动态规划，都是可以从暴力尝试优化来的，所以还是先来一个暴力递归的版本

//返回从i,j出发，到达最右下角的位值的最小路径和 int walk(vector<vector<int>> &matrix, int i, int j) { if (i == matrix.size() - 1 && j == matrix[0].size() - 1) { return matrix[i][j]; } //只能往右走 if (i == matrix.size() - 1) { return matrix[i][j] + walk(matrix, i, j + 1); } //只能往下走 if (j == matrix[0].size() - 1) return matrix[i][j] + walk(matrix, i + 1, j); //右边位值到右下角的最小路径和 int right = walk(matrix, i, j + 1); //下边位值到右下角的最小路径和 int down = walk(matrix, i + 1, j); return matrix[i][j]+min(right,down); }

显然这个方法的代价是很高的，很多位值的点都被重复递归展开过，所以现在可以尝试，设计一种缓存机制，把递归展开过的点都做过记录，下次再遇到时，直接从缓存里拿数据，而不是递归展开

当我们遇到动态规划时，第一步不可忽略的步骤，是去写递归的尝试方法，再从尝试方法中分析出可变参数，比如这道题，我们的可变参数就是i和j，可变参数是几维的，我们充当缓存的 表，就是几维的，把最终要求的状态在表中标记出来，以这道题为例 假设有如下的二维数组：

要画它的状态转移图，找到最终的状态，标出来，然后根据base case，把不依赖状态的值，设置好，对于这道题就是，最后一行和最后一列 然后分析普遍位置，是如何依赖的，这道题中(i,j)位置的值，会依赖它右边和它下面的位值的值，因此根据最后一行和最后一列，能确定这张表中的所有状态，推到（0，0）位值时，就拿到了我们想要的值。 这其实就是暴力递归改动态规划的统一套路，下面看dp代码

int minPath(vector<vector<int>>&matrix){ int row=matrix.size(); int col=matrix[0].size(); int dp[row][col]; dp[0][0]=matrix[0][0]; for(int i=1;i<row;i++){ dp[i][0]=dp[i-1][0]+matrix[i][0]; } for(int i=1;i<col;i++){ dp[0][i]=dp[0][i-1]+matrix[0][i]; } for(int i=1;i<row;i++){ for(int j=1; j<col; j++){ dp[i][j] = min(dp[i-1][j],dp[i][j-1]+matrix[i][j]); } } return dp[row-1][col-1]; }

例2：

给你一个数组 arr，和一个整数aim。如果可以任意选择arr中的数字，能不能累加得到aim，返回true或者false .

暴力递归：数组每个位置的数，都对应加或者不加两个状态，两个状态中只要有一个返回true，就说明能得到aim，函数返回true。

bool isSum(vector<int>&arr, int i, int sum,int aim){ if(arr.size()==i){ return aim==sum; } return isSum(arr,i+1,sum,aim)||isSum(arr,i+1,sum+arr[i],aim); }

动态规划： 可变参数：i，sum 后效性：无 状态转移图：二维

bool isSum(vector<int>&arr,int aim){ int rol=arr.size()+1; int col=aim+1; bool dp[rol][col]; for(int i=0;i<rol;i++){ dp[i][aim]=true; } for(int i=arr.size()-1;i>=0;i--){ for(int j=aim-1;j>=0;j--){ dp[i][j]=dp[i+1][j]; if(j+arr[i]<=aim){ dp[i][j]=dp[i][j]||dp[i+1][j+arr[i]]; } } } return dp[0][0]; }