显然我们很容易用递归实现但是会超时的因为计算第n个位置的斐波那契数的大小时会重复很多次的计算某些位置的斐波那契数因此如果我们能记录下已经计算过的位置对应的斐波那契数时当再次需要该位置的斐波那契数时就不用再重复的进行计算了。

class

memo[n];}memo[n](dfs(n-1)dfs(n-2))%1000000007;return

memo[n];}

dp[i](dp[i-1]dp[i-2])%1000000007;

return

本道题很容易使用递归实现但是会超时原因同上一道题一样会大量重复的计算一些以某些位置为起点到终点的路径数而且时间复杂度是呈指数级别的因此我们可以和上一道题一样如果将已经计算过的以某些位置为起点到终点的路径数记录下来当再次求以这些位置为起点到终点的路径数时直接使用即可避免了大量的重复计算。

class

1;}else{memo[x][y]dfs(x-1,y,memo)dfs(x,y-1,memo);return

memo[x][y];}}

j1;jn;j){dp[i][j]dp[i-1][j]dp[i][j-1];}}return

dp[m][n];}

这道题已经在之前的博客中写过了之前使用的是动态规划和贪心二分之前的动态规划是从前往后分析的下面将使用递归记忆化搜素以及从后往前的分析的动态规划。

递归记忆化搜素

从头到尾扫描数组分别计算以该位置为起点的最长递增子序列的长度并把每次计算好的结果进行记录当下次再次用到以已记录位置为起点的最长递增子序列的长度时直接拿已经计算好的结果即可避免了不少重复的计算。

可以说是在分析前面的递归记忆化搜素方法的基础上摸索出来的如何定义状态表示和状态转移方程等这里不再赘述可以参考之前的博客。

class

i0;inums.size();i)retmax(ret,dfs(i,nums,memo));return

ret;}int

ipos1;inums.size();i)if(nums[i]nums[pos])kmax(k,dfs(i,nums,memo)1);memo[pos]k;return

k;}

ji1;jn;j){if(nums[i]nums[j])dp[i]max(dp[i],dp[j]1);}return

*max_element(dp.begin(),dp.end());}

};//动态规划

上面之所以没有截示例是因为示例比较长而且文字描述很多比较容易看晕下面也是采用递归记忆化搜素来解决因为如果只使用递归会超时因为会大量的重复计算相同位置的值如果能够将每次计算好的值保存起来下次使用时直接取就能够较少大量的操作更佳。

从头到尾扫描整个数组分别计算以该位置为起点的最大花费然后计算所有起始位置的最大花费的最小值。

class

ydfs(head1,right);retmin(ret,headmax(x,y));}memo[left][right]ret;return

ret;}

下面也是采用递归记忆化搜素来解决因为如果只使用递归会超时因为会大量重复计算以某位置为起点的最长递增路径如果能够记录下以某位置为起点的最长递增路径当下次使用时直接取即可就能够减少大量的重复计算以示例1为例比如就以【2】【1】位置的1为起始位置计算时会有一条向上到6的路径但是如果已经计算过以这个6为起始位置的最长递增路径的长度可以直接使用就不用再重复计算了。

class

longestIncreasingPath(vectorvectorint

matrix)

ret0;nmatrix.size(),mmatrix[0].size();for(int

i0;in;i)for(int

j0;jm;j)retmax(ret,dfs(matrix,i,j));return

ret;}int

matrix[x][y]matrix[i][j])retmax(ret,dfs(matrix,x,y)1);}maxlen[i][j]ret;return

ret;}