动态规划-面试题
基本思想
和分支法一样，动态规划是通过组合子问题的解而解决整个问题的。分值算法时将问题划分为一个或多个相互独立的子问题，递归的求解各个子问题，然后合并子问题的解从而得到原问题的解，例如递归排序。动态规划适用于子问题不是独立的情况（重叠子问题），也就是说各个子问题又包含公共的子子问题。在这种情况下，如果用分支算法则会做许多不必要的工作，即重复求解公共的子子问题。
动态规划算法将每个子子问题只求解一次，并将结果保存在一个表中，从而避免重复计算相同的子子问题。
最优子结构
如果一个问题的一个最优解中包含了子问题的最优解，则该问题具有最优子结构。当问题具有最优子结构时，就提示我们动态规划可能适用，对于特定的问题也可以适用贪心算法解决。
在寻找最优子结构时，可以遵循一种共同的模式
1、将问题视为一系列选择，对问题做一个选择，将会得到一个或多个待解决的子问题。
2、假定我们已知一个可以导致最后解的子问题（不必关心如何确定该子问题），然后做出选择，从而确定哪些子子问题会随之产生以及如何最好的描述所得到的子子问题空间。
问题空间
构造原问题的一个最优解所需要的多个子问题。
备忘录方法
动态规划算法的一种变形，采用自顶向下的策略求解动态规划问题。其思想是通过备忘录优化原问题低效的自底向上的算法，因为自底向上的动态规划算法一般会计算所有的子问题（因为无法预知哪些子问题不需要求解），而自顶向上的的算法中，只有我们在递归过程中碰到了特定的子问题我们才对其计算。因此，像一般动态规划算法一样，也是维护一个记录子问题解的表。
在实际项目中，如果所有子问题都至少需要计算一次，则自底向上的动态规划算法要比自顶向下的备忘录方法好出一个常量因子。
但是，如果子问题空间中的某些子问题根本没必要求解，备忘录方法将只会求解必要的子问题，即在递归过程中遇到的子问题。
面试题
分析
定义：f( n)表示n个台阶的爬台阶的方法数
选择：上一步爬了一步还是爬了两步
初始化：f(0)=1,f(1)=1
递推表达：f(n)=f(n-1)+f(n-2),n>=2
注：该问题类似于求解斐波那契数列（Fibonacci sequence）。斐波那契数列从0开始：0,1,1,2,3,5...，此问题解为1,1,2,3,5,....
public int climbStairs(int n) {
if(n<=1) return 1;
int[] fibonacci=new int[n+2];
fibonacci[0]=0;fibonacci[1]=1;
for(int i=2;i<=n+1;i++){
fibonacci[i]=fibonacci[i-1]+fibonacci[i-2];
}
return fibonacci[n+1];
}
定义：min[i]表示第i天前最低股票价格，i>=1（i从0开始）
初始化：min[0]=prices[0]，便于边界处理
递推表达式：min[i]=MIN{min[i-1],prices[i]}，i>=1（i从0开始）
求解：遍历求解每一天出售可获取的最大利润，最后返回最大值利润。
public int maxProfit(int[] prices) {
if(prices.length<2) return 0;
int[] minBefore=new int[prices.length];
minBefore[0]=prices[0];
for(int i=1;i
分析
定义：sum[i]表示nums[0]~nums[i]的和，i>=1
初始化：sum[0]=nums[0]，便于边界处理
递归表达式：sum[i]=sum[i-1]+nums[i]，i>=1
public class NumArray {
private int[] nums;
private int[] sumBefore;
public NumArray(int[] nums) {
this.nums=nums;
if(nums.length!=0){
this.sumBefore=new int[nums.length];
solve();
}
}
public int sumRange(int i, int j) {
if(nums.length==0) return 0;
return nums[i]+sumBefore[j]-sumBefore[i];
}
private void solve(){
sumBefore[0]=nums[0];
int sum=nums[0];
for(int i=1;i
分析
定义：count[i]表示a[0]~a[i]解码次数
初始化：根据规则计算count[0]和count[1]，count[i]=0
递推表达式：
1、如果a[i]可以单独解码（1~9），count[i]+=count[i-1]
2、如果a[i-1]a[i]可以联合解码（10~26），count[i]+=count[count-2]
public int numDecodings(String s) {
if(s.length()==0)return 0;
if(s.length()==1){
return s.charAt(0)=='0'?0:1;
}
int[] count=new int[s.length()];
count[0]=s.charAt(0)=='0'?0:1;
if(s.charAt(1)!='0'){
count[1]+=count[0];
}
if(s.charAt(0)=='1'||(s.charAt(0)=='2'&&s.charAt(1)<='6')){
count[1]+=1;
}
for(int i=2;i
分析
定义：d[i]表示以a[i]结尾的最长上升子序列长度。
初始化：d[i]=1，每个元素构成一个序列
递推表达式：d[i]=MAX{d[i],d[j]+1}，其中j
public int lengthOfLIS(int[] nums) {
if(nums.length==0) return 0;
return maxLengthIncreasing(nums).size();
}
public List maxLengthIncreasing(int[] a){
int[] d=new int[a.length];
//初始化
for(int i=0;id[maxIndex]){
maxIndex=i;
}
}
//解析结果
List res=new ArrayList();
res.add(a[maxIndex]);
int nextIndex=maxIndex;
for(int i=maxIndex-1;i>=0;i--){
if(d[i]+1==d[nextIndex]&&a[i]
分析
方案一
定义：d[i]表示以a[i]结尾的子序列的最大和
初始化：d[0]=a[0]
递推表达式：d[i]=MAX{d[i-1]+a[i]，a[i]}，i>0
public int maxSubArray(int[] nums) {
if(nums.length==0) return 0;
int[] d=new int[nums.length];
d[0]=nums[0];
for(int i=1;i方案二
我们确定需要一个数组来记录以每个位置结尾的序列的最大和吗？空间复杂度是否可以进行优化？
我们可以用一个变量currentMax表示以当前元素为末尾的子序列的最大和。currentMax=max{a[i],a[i]+currentMax}，用另一个变量max记录历史最大和。遍历过程中不断更新max即可。
public int maxSubArray(int[] nums) {
if(nums.length==0) return 0;
int currentMax=nums[0],max=nums[0];
for(int i=1;i
//每一时刻，我们只需要保留当前的极值，只有极大值和极小值才可能组合成最终的结果
public int maxProduct(int[] A) {
if (A.length == 0) {
return 0;
}
int maxherepre = A[0];
int minherepre = A[0];
int maxsofar = A[0];
int maxhere, minhere;
for (int i = 1; i < A.length; i++) {
maxhere = Math.max(Math.max(maxherepre * A[i], minherepre * A[i]), A[i]);
minhere = Math.min(Math.min(maxherepre * A[i], minherepre * A[i]), A[i]);
maxsofar = Math.max(maxhere, maxsofar);
maxherepre = maxhere;
minherepre = minhere;
}
return maxsofar;
}
分析
方案一
暴力破解，对于所以字符串s[i]~s[j]，0<=i<=j<=n，判定其是否为回文串。时间复杂度O(n^3)
方案二
中心扩展法，对任意字符s[i]，以s[i]为中心向两端进行扩展，求得最长回文长度。
注：为了方便对于奇数长度回文串和偶数长度回文串进行统一处理，我们将字符串的每个字符中间填充特殊符号‘*’，例如“abbad”填充后为“*a*b*b*a*d*”。
public String longestPalindrome(String s) {
if(s.length()==0) return "";
char[] cs=new char[s.length()*2+1];
cs[0]='*';
int index=1;
for(int i=0;i=0&&end<=cs.length-1&&cs[start]==cs[end]){
if(end-start>maxEnd-maxStart){
maxEnd=end;
maxStart=start;
}
start--;
end++;
}
}
StringBuilder builder=new StringBuilder();
for(int i=maxStart;i<=maxEnd;i++){
if(cs[i]!='*')
builder.append(cs[i]);
}
return builder.toString();
}
方案三
对于方案一显然会有很多重复的计算，例如，s[i]~s[i]不为回文，s[i-k]~s[j+k]均不是回文。我们可以利用动态规划避免重复计算。
空间复杂度O(n^2)，时间复杂度O(n^2)。虽然比方案一高效，但是不如方案二。
定义：d[i][j]表示s[i]~s[j]是否是回文串。
初始化：
d[i][j]=true，i=j
d[i][j]=false，i
递推表达式：
当s[i]!=s[j]，d[i][j]=false
当s[i]==s[j]，d[i][j]=d[i-1][j-1]
public String longestPalindrome1(String s) {
if(s.length()==0)return "";
char[] cs=new char[s.length()*2+1];
cs[0]='*';
int index=1;
for(int i=0;imaxEnd-maxStart+1){
maxStart=row;
maxEnd=col;
}
d[row++][col++]=true;
}else{
d[row++][col++]=false;
}
}
}
StringBuilder builder=new StringBuilder();
for(int i=maxStart;i<=maxEnd;i++){
if(cs[i]!='*')
builder.append(cs[i]);
}
return builder.toString();
}
分析
定义：d[i]表示s[0]~s[i]的最小分割次数
初始化：d[i]=i，0<=i
递推表达式：
如果s[0]~s[j]为回文，d[i]=0
否则，d[i]=MIN{d[j]+1}，其中j
注：为了加快s[j]~s[i]是否为回文的判断，我们先利用上题中的动态规划思想，求出所有s[j]~s[i]是否为回文的结果。
public int minCut(String s) {
int n=s.length();
if(s.length()<=1) return 0;
//isPalin[i][j]=ture表示s[i]~s[j]是回文，否则不是
boolean[][] isPalin=new boolean[n][n];
//单个字符为回文
for(int i=0;i=0;i--){
for(int j=i+2;j
There are a row ofnhouses, each house can be painted with one of the three colors: red, blue or green. The cost of painting each house with a certain color is different. You have to paint all the houses such that
no two adjacent houses have the same color.
The cost of painting each house with a certain color is represented by anx3cost matrix. For example,costs[0][0]is
the cost of painting house 0 with color red;costs[1][2]is the cost of painting house 1 with color green, and so on... Find the minimum cost to paint all houses.
Note:
All costs are positive integers.
There are a row ofnhouses, each house can be painted with one of thekcolors. The cost of painting each house with a certain color is different. You have to paint all
the houses such that no two adjacent houses have the same color.
The cost of painting each house with a certain color is represented by anxkcost matrix. For example,costs[0][0]is
the cost of painting house 0 with color 0;costs[1][2]is the cost of painting house 1 with color 2, and so on... Find the minimum cost to paint all houses.
Note:
All costs are positive integers.
Follow up:
Could you solve it inO(nk) runtime?
分析
定义：d[i][j]表示h[i]刷c[i]时的刷墙总成本
初始化：d[0][j]=cost[0][j]，0<=j
分析
最小化数组乘积
递推表达式：
d[i][j]=MIN{d[i-1][k]+cost[i][k]}，其中k!=j
public int minCost(int[][] cost){
if(cost.length==0) return 0;
int H=cost.length,C=cost[0].length;
//d[i][j]表示h[i]刷c[j]时的h[0]~h[i]最小成本
int[][] d=new int[H][C];
for(int c=0;c最长公共子序列
分析
定义：d[i][j]表示s[0]~s[i-1]与t[0]~t[j-1]最长公共子序列的长度
初始化：d[i][j]=0，i=0或j=0，便于边界处理
递推关系式：
当s[i-1]=t[j-1]时，d[i][j]=d[i-1][j-1]+1，1<=i<=s.length,1<=j<=t.length
否则，d[i][j]=MAX{d[i][j-1],d[i-1][j]}
public String lcs(String s,String t){
if(s.length()==0||t.length()==0){
return "";
}
int m=s.length(),n=t.length();
int[][] d=new int[m+1][n+1];
//初始化
for(int i=0;i<=m;i++) d[i][0]=0;
for(int j=0;j<=n;j++) d[0][j]=0;
//迭代求解
for(int i=1;i<=m;i++){
for(int j=1;j<=n;j++){
if(s.charAt(i-1)==t.charAt(j-1)){
d[i][j]=d[i-1][j-1]+1;
}else{
d[i][j]=Math.max(d[i][j-1], d[i-1][j]);
}
}
}
//反向解析结果
StringBuilder res=new StringBuilder();
int row=m,col=n;
while(row>=1&&col>=1){
if(s.charAt(row-1)==t.charAt(col-1)){
res.append(s.charAt(row-1));
row--;col--;
}else{
if(d[row][col-1]>d[row-1][col]){
col--;
}else{
row--;
}
}
}
return res.reverse().toString();
}
最长公共子串
分析
分析
定义：d[i][j]表示以s[i-1]结尾的子串与t[j-1]结尾的子串最大公共长度
初始化：d[i][j]=0，i=0或j=0，方便边界处理
递推表达式：
当s[i-1]=t[j-1]时，d[i][j]=d[i-1][j-1]+1
否则，d[i][j]=0
public String lcs(String s,String t){
if(s.length()==0||t.length()==0){
return "";
}
int m=s.length(),n=t.length();
int[][] d=new int[m+1][n+1];
//初始化
for(int i=0;i<=m;i++) d[i][0]=0;
for(int j=0;j<=n;j++) d[0][j]=0;
int maxi=-1,maxj=-1,maxLength=Integer.MIN_VALUE;
for(int i=1;i<=m;i++){
for(int j=1;j<=n;j++){
if(s.charAt(i-1)==t.charAt(j-1)){
d[i][j]=d[i-1][j-1]+1;
if(d[i][j]>maxLength){
maxi=i;maxj=j;maxLength=d[i][j];
}
}else{
d[i][j]=0;
}
}
}
if(maxi==-1){
return "";
}else{
return s.substring(maxi-maxLength,maxi);
}
}
分析
定义：d[i][j]表示s[0]~s[i-1]中t[0]~t[j-1]出现的次数
初始化：d[i][0]=1,0<=i<=m，便于边界处理
递推表达式：
当i
当s[i-1]=t[j-1]时，d[i][j]=d[i-1][j-1]+d[i-1][j]，i>=j
否则，d[i][j]=d[i-1][j]，i>=j
注意：对于边界值的确定，我们可以举特殊例子来判定，例如j=1时的所有情况。此外我们还可以先将边界值计算出来，再进行递推表达式的计算。
public int numDistinct(String s, String t) {
if(s.length()==0||t.length()==0||s.length()
分析
定义：d[i][j]表示s[0]~s[j-1]与t[0]~t[j-1]最小编辑距离
初始化：d[i][0]=i，d[0][j]=j
递推表达式：
当s[i-1]=t[j-1]，d[i][j]=d[i-1][j-1]
否则，d[i][j]=1+MIN{d[i][j-1],d[i-1][j],d[i-1][j-1]}
注：d[i][j-1]表示在s[i]后面插入一个与t[j]相等的字符然后同时消掉（或者说将t[j]删除）。d[i-1][j]与d[i][j-1]同理。d[i-1][j-1]表示将s[i]替换成了t[j]然后同时消除。
public int minDistance(String word1, String word2) {
if(word1.length()==0){
return word2.length();
}
if(word2.length()==0){
return word1.length();
}
int m=word1.length(),n=word2.length();
int[][] d=new int[m+1][n+1];
for(int i=0;i<=m;i++)d[i][0]=i;
for(int j=0;j<=n;j++) d[0][j]=j;
for(int i=1;i<=m;i++){
for(int j=1;j<=n;j++){
if(word1.charAt(i-1)==word2.charAt(j-1)){
d[i][j]=d[i-1][j-1];
}else{
d[i][j]=1+Math.min(d[i-1][j-1], Math.min(d[i-1][j], d[i][j-1]));
}
}
}
return d[m][n];
}
分析
定义：d[i][j]=true表示s3[0]~s3[i+j-1]能由s1[0]~s1[i-1]和s2[0]~s2[j-1]
初始化：d[0][0]=true
递推表达式：
如果s1[i-1]=s3[i+j-1]且d[i-1][j]=true，那么d[i][j]=true
如果s2[j-1]=s3[i+j-1]且的d[i][j-1]=true，那么d[i][j]=true
否则，d[i][j]=false
public boolean isInterleave(String s1, String s2, String s3) {
if(s1.length()+s2.length()!=s3.length()){
return false;
}
int m=s1.length(),n=s2.length(),k=s3.length();
boolean[][] d=new boolean[m+1][n+1];
d[0][0]=true;
for(int i=0;i<=m;i++){
for(int j=0;j<=n;j++){
if(i==0&&j==0){
continue;
}
if(i-1>=0&&d[i-1][j]&&s1.charAt(i-1)==s3.charAt(i+j-1)){
d[i][j]=true;
}
if(j-1>=0&&d[i][j-1]&&s2.charAt(j-1)==s3.charAt(i+j-1)){
d[i][j]=true;
}
}
}
return d[m][n];
}
思考：如果是更一般的情况，s1和s2不是正好交替组合成s3，而是可能有多余的字符呢？
public boolean isInterleave(String s1, String s2, String s3) {
if(s1.length()+s2.length()!=s3.length()){
return false;
}
//d[i][j]表示s1前i个字符和s2前j个能交替表示s3的前d[i][j]个字符
int m=s1.length(),n=s2.length(),k=s3.length();
int[][] d=new int[m+1][n+1];
for(int i=0;i<=m;i++){
for(int j=0;j<=n;j++){
int max=0;
if((i>0&&d[i-1][j]>=k)||(j>0&&d[i][j-1]>=k))
max=k;
if(i>0&&s1.charAt(i-1)==s3.charAt(d[i-1][j])){
max=Math.max(max, d[i-1][j]+1);
}
if(j>0&&s2.charAt(j-1)==s3.charAt(d[i][j-1])){
max=Math.max(max, d[i][j-1]+1);
}
d[i][j]=max;
}
}
return d[m][n]==k;
}
最小化数组乘积
给出两个数组A和B，两个数组大小分别是m和n，其中m
例如A={1,-1},B={1,2,3,4}，A'={1,0,0,-1}，A'*B=-3，因此最小化乘积为-3。
分析
定义：d[i][j]表示A[0]~A[i-1]与B[0]~B[j-1]的最小乘积
初始化：d[0][j]=0
递推表达式
d[i][j]=MIN{d[i-1][j-1]+A[i-1]*B[j-1],d[i][j-1]}
注：d[i-1][j-1]+A[i-1]*B[j-1]表示A[i-1]与B[j-1]相乘。d[i][j-1]表示B[j-1]与0相乘，其中j>i。
public int minMultiply(int[] a,int [] b){
int m=a.length,n=b.length;
int[][] d=new int[m+1][n+1];
for(int i=1;i<=m;i++){
for(int j=i;j<=n;j++){
if(j==i){
d[i][j]=d[i-1][j-1]+a[i-1]*b[j-1];
}else{
d[i][j]=Math.min(d[i-1][j-1]+a[i-1]*b[j-1], d[i][j-1]);
}
}
}
return d[m][n];
}
分析
定义：d[i][j]表示a[0][0]到a[i][j]的最小路径和
初始化：直接计算i=0和j=0的结果
递推表达式：d[i][j]=a[i][j]+MIN{d[i][j-1],d[i-1][j]}，i>=1且j>=1
public int minPathSum(int[][] grid) {
if(grid.length==0||grid[0].length==0) return 0;
int m=grid.length,n=grid[0].length;
int[][] d=new int[m][n];
int sum=0;
for(int i=0;i
分析
定义：d[i][j]表示从g[0][0]到g[i][j]的路径数
初始化：d[i][j]=1,i=0或j=0
递推表达式：d[i][j]=d[i-1][j]+d[i][j-1]，i>=1且j>=1
public int uniquePaths(int m, int n) {
if(m==0||n==0)
return 1;
int[][] d=new int[m][n];
for(int i=0;i
分析
定义：d[i][j]表示从g[0][0]到个g[i][j]的路径。
初始化：计算i=0或j=0的结果
递推表达式：
如果g[i][j]=1，则d[i][j]=0
否则，d[i][j]=d[i-1][j]+d[i][j-1]，i>=1且j>=1
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
if(obstacleGrid.length==0&&obstacleGrid[0].length==0){
return 0;
}
if(obstacleGrid[0].length==0){
return 1;
}
int m=obstacleGrid.length,n=obstacleGrid[0].length;
int[][] d=new int[m][n];
d[0][0]=(obstacleGrid[0][0]==1)?0:1;
for(int i=1;i
分析
定义：d[i][j]表示从a[0][0]到a[i][j]的最小路径和，其中j<=i
初始化：计算d[i][0]
递推表达式：
如果i=j，d[i][j]=a[i][j]+d[i-1][j-1]
否则d[i][j]=a[i][j]+MIN{d[i-1][j],d[i-1][j-1]}
public int minimumTotal(List<>> triangle) {
if(triangle.size()==0||triangle.get(0).size()==0){
return 0;
}
int m=triangle.size(),n=m;
int[][] d=new int[m][n];
int sum=0;
for(int i=0;i改进
我们确定需要O(n^2)的额外空间吗？我们迭代的方向是一直向下，并且我们的最终结果就保存在我们最后一次迭代的结果里面。
显然，我们可以将空间复杂度降为O（n）。上面一些题目中如果迭代方向是单向的并且不需要全局搜寻最优解，一样可以优化。
public int minimumTotal(List<>> triangle) {
if(triangle.size()==0||triangle.get(0).size()==0){
return 0;
}
int n=triangle.size();
int[] d=new int[n];
int[] pre=new int[n];
d[0]=triangle.get(0).get(0);
for(int row=1;row
分析
定义：d[n]表示节点个数为n个二分查找树的种数。
初始化：d[0]=1,d[1]=1
递推表达式：d[n]=∑(d[k]*d[n-k-1])，0<=k<=n-1,k表示左子树节点数目
public int numTrees(int n) {
if(n<=1)return 1;
int[] nums=new int[n+1];
nums[0]=1;nums[1]=1;
for(int i=2;i<=n;i++){
int sum=0;
for(int j=0;j
分析
如果允许O(n log n)的复杂度，那么我们可以先进行排序，但是本题要求时间复杂度O(n)。
对于无序元素的处理，并且要求时间复杂度O(n)，我们首先要想到哈希表。如果我们用一个哈希表记录元素是否使用过，然后以每个元素为中心往左右扩展，直到不连续为止，记录下历史最长连续长度。显然会涉及到很多重复的扩展，最坏时间复杂度为O(n^2)，不符合题目要求。因此我们需要想办法避免这样的重复扩展。
例如，对于元素X只往左边扩展（只考虑小于等于它的连续序列），然后记录下左边连续长度。当下次处理X+1时，只需将X向左边连续长度+1。这样时间复杂度就降低为了O(n)。
public int longestConsecutive(int[] nums) {
if(nums.length==0) return 0;
Map markMap=new HashMap();
for(int i=0;i
Map countMap=new HashMap();
for(int i=0;i
此外，我们还可以利用备忘录方法，递归处理该问题。当连续序列长度过长时，递归调用深度过深将会导致栈溢出。仅供参考。
public int longestConsecutive(int[] nums) {
if(nums.length==0) return 0;
Map lengthMap=new HashMap();
for(int i=0;imax){
max=lengthMap.get(nums[i]);
}
}
return max;
}
private void solveLength(int n,Map lengthMap){
if(lengthMap.get(n).equals(0)){//还没有处理过
if(lengthMap.get(n-1)!=null){//n-1存在，先处理n-1的连续长度
solveLength(n-1,lengthMap);
lengthMap.put(n, lengthMap.get(n-1)+1);
}else{
lengthMap.put(n, 1);
}
}
}
相关文章
图文推荐
- 文章
- 推荐
- 热门新闻