剑指 Offer II 80-100(持续更新)涵盖哪些面试题，你能一一解答吗？
- 内容介绍
- 文章标签
- 相关推荐
本文共计7756个文字，预计阅读时间需要32分钟。
剑指 Offer II 100：三角形中最小路径之和 + 给定一个三角形 triangle，找出从顶部到底部的最小路径和。每一步只能移动到下一行中相邻的结点上。相邻的结点在这里指的是在同一行上、左或右紧挨着的结点。
剑指 Offer II 100：三角形中最小路径之和给定一个三角形 triangle ，找出自顶向下的最小路径和。
每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。也就是说，如果正位于当前行的下标 i ，那么下一步可以移动到下一行的下标 i 或 i + 1 。
示例 1：
输入：triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
输出：11
解释：如下面简图所示：
2
3 4
6 5 7
4 1 8 3
自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。示例 2：
示例2：
输入：triangle = [[-10]]
输出：-10
提示：
- 1 <= triangle.length <= 200
- triangle[0].length == 1
- triangle[i].length == triangle[i - 1].length + 1
- -104 <= triangle[i][j] <= 104
就直接递归所有的可能 去获得最小的那个 很明显过不了最后一个用例。
class Solution {
int min = Integer.MAX_VALUE;
public int minimumTotal(List<List<Integer>> triangle) {
if(triangle.size()==1){
return triangle.get(0).get(0);
}
getRES(triangle,1,0,triangle.get(0).get(0));//第0层 第0个 前面路线的和为0
return min;
}
public void getRES(List<List<Integer>> triangle,int level,int index,int res){
if(level==triangle.size()-1){
min=Math.min(min,Math.min(triangle.get(level).get(index)+res,triangle.get(level).get(index+1)+res));
return;
}
getRES(triangle,level+1,index,res+triangle.get(level).get(index));
getRES(triangle,level+1,index+1,res+triangle.get(level).get(index+1));
}
}
这里我模糊的记忆告诉我优化需要根据输入的维数，而我的输入有4个，数组、遍历的层数(到第几层了)、当前索引到多少了、和是多少。
我就以为需要搞个四维的东西，其实不然，我们可以直接通过建立一个相同大小的二维数组，根据这个可以保存之前走过的值，而不是通过系统栈的递归重复去进行计算，有点像斐波那契数列的空间保存优化。
这里就有了我们的解法二：通过dp数组优化。
解法二：dp数组 空间O(N2)我们每次通过数组记录我们之前的选择。首先自下而上（这个思路很重要，斐波那契数列问题也是这样优化的）的去思考，会发现每个位置(假设为i)都只能从上一层的该位置或者i-1位置过来，而且这条路径一定会加上当前层i位置值，我们只需要从上一层的这两个数中挑选较小的即可。
class Solution {
public int minimumTotal(List<List<Integer>> triangle) {
if(triangle.size()==1){
return triangle.get(0).get(0);
}
//经典dp做法 因为当前行的大小可以根据上一行中对应位置的元素得到
//用i j表示横纵坐标，每一行j<=i 把数字向左对齐是一个等腰直角三角形
//但是当处于每行中的0位置和最右位置时，数据可以直接得出 即上一行最左侧的路径和和最右侧的路径和
//其余的时候得判断一下两个中的较小值
int n = triangle.size();
int[][] res = new int[n][n];
int i=0,j=0;
res[0][0] = triangle.get(0).get(0);
for(i=1;i<n;i++){//从1开始遍历 因为(0,0)的路径和就是自己
//每一行0处的公式：res(i,0)=res(i-1,0)+triangle(i,0)
res[i][0]=res[i-1][0]+triangle.get(i).get(0);
for(j=1;j<i;j++){//这里是小于i 因为等于i的要特殊判定
//在第二行的时候 直接跳过这里了，因此从第三行才开始执行这个循环
res[i][j]=Math.min(res[i-1][j-1],res[i-1][j])+triangle.get(i).get(j);
}
//每一行i处的公式：res(i,i)=res(i-1,i-1)+triangle(i,i)
res[i][i]=res[i-1][i-1]+triangle.get(i).get(i);
}
int min = res[n-1][0];
for(i=1;i<n;i++){
min=Math.min(min,res[n-1][i]);
}
return min;
}
}
解法三：优化dp数组至空间O(N)
这里我们观察数组可以意识到，我们数据与数据之间只有上下一行有关系，因此我们有了优化做法，用两个长度为n的数组，左脚踩右脚完成所有路径和的叠加。(这里我们可以意识到，每个路径都需要走到最下面的一层，因此每个路径是可以自下而上的去探索规律的)。
class Solution {
public int minimumTotal(List<List<Integer>> triangle) {
if(triangle.size()==1){
return triangle.get(0).get(0);
}
//优化做法 用两个长度为n的数组 左脚踩右脚完成
int n = triangle.size();
int[] a = new int[n];
int[] b = new int[n];
int i=0,j=0;
a[0] = triangle.get(0).get(0);//a永远是旧的那个
for(i=1;i<n;i++){//b永远是新的那一个行
//每一行0处的公式：b(0)=a(0)+triangle(i,0)
b[0]=a[0]+triangle.get(i).get(0);
for(j=1;j<i;j++){//这里是小于i 因为等于i的要特殊判定
//在第二行的时候 直接跳过这里了，因此从第三行才开始执行这个循环
b[j]=Math.min(a[j-1],a[j])+triangle.get(i).get(j);
}
//每一行i处的公式：res(i,i)=res(i-1,i-1)+triangle(i,i)
b[i]=a[i-1]+triangle.get(i).get(i);
//交换a和b的指向
int[] c = a;
a=b;
b=c;
}
//因为最后的交换 现在a是结果行
int min = a[0];
for(i=1;i<n;i++){
min=Math.min(min,a[i]);
}
return min;
}
}
这里的数组是用到了两个长度为N的数组，a和b。那么我们能不能继续进行优化呢？答案当然是可以的，我们可以只用一个数组就完成遍历，这就是解法四。
解法四：一个数组完成我们前几种方法的遍历，是通过每一行从左到右去生成下一行的内容，这样我们每个数据会依赖上一个行的上侧和左侧。那么我们换一种思路去遍历，从右至左的遍历，又可以剩下一个数组的空间：
每个数据只依赖上一行的上和左，我们将所有数据在一行上更新的话，从右往左走，每次最右侧的数据只依赖上一行的最右侧，每新的一行都要比上一行多一个，那么最右侧的i位置，只依赖上一行的i-1位置，即左侧的值。而右侧第二个数i-1位置，依赖上和左，而上就是当前i-1位置的值，左是i-2位置的值，从而我们可以更新i-1位置的值。
因此，我们可以通过一个数组去完成这个任务。
class Solution {
public int minimumTotal(List<List<Integer>> triangle) {
if(triangle.size()==1){
return triangle.get(0).get(0);
}
//优化做法 用一个长度为n的数组 从右到左遍历完成
int n = triangle.size();
int[] res = new int[n];
int i=0,j=0;
res[0] = triangle.get(0).get(0);
for(i=1;i<n;i++){
//i不变 还是从上往下遍历 j需要从最大往最小遍历即从右到左
//因此需要先把i位置的值搞上 最后搞0位置的值
res[i]=res[i-1]+triangle.get(i).get(i);
for(j=i-1;j>0;j--){
res[j]=Math.min(res[j-1],res[j])+triangle.get(i).get(j);
}
res[0]=res[0]+triangle.get(i).get(0);
}
int min = res[0];
for(i=1;i<n;i++){
min=Math.min(min,res[i]);
}
return min;
}
}
总结
- 要学会自下而上的思考方式，根据这个再从上往下走。
- 学到了dp的优化，去找数据之间的依赖关系。
- 根据依赖关系再去进行空间的优化。
- 多去尝试遍历方式能否继续优化，对空间的利用可以做到极致。
给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
说明：一个机器人每次只能向下或者向右移动一步。
示例 1：
输入：grid = [[1,3,1],[1,5,1],[4,2,1]]
输出：7
解释：因为路径 1→3→1→1→1 的总和最小。
示例 2：
输入：grid = [[1,2,3],[4,5,6]]
输出：12
提示：
- m == grid.length
- n == grid[i].length
- 1 <= m, n <= 200
- 0 <= grid[i][j] <= 100
注意：本题与主站 64 题相同： leetcode-cn.com/problems/minimum-path-sum/
解法一：暴力解老规矩，先试试暴力解法。
class Solution {
int min = Integer.MAX_VALUE;
public int minPathSum(int[][] grid) {
//暴力解
help(grid,0,0,0);
return min;
}
public void help(int[][] grid,int i,int j,int res) {
if((i==grid.length-1)&&(j==grid[0].length-1)){
res+=grid[grid.length-1][grid[0].length-1];
min=Math.min(min,res);
return;
}
if(i>grid.length-1||j>grid[0].length-1){
return;
}
help(grid,i+1,j,res+grid[i][j]);
help(grid,i,j+1,res+grid[i][j]);
}
}
经典不给过嗷，现在去想咋用dp去做优化。
解法二：dp数组这里我们直接一步到位，先分析这个问题，主要还是搞路径和对吧，那么我们就可以给中间状态的每一步去记录下来，就想到了用一个一样大小的数组去记录。首先是第一行和第一列的路径和是固定的，只能这么走（因为规定了是最短路径，且方格中每个数都大于0，那么每多走一步都会浪费，在边上的相邻的两个数肯定是直接走是最近的）。
因此我们可以先把第一行和第一列的结果求出来。然后挨个去求每一行的路径和，每个地方只需要去判断左和上哪个更小，哪个更小就加到自己就形成了最小的当前路径和，和第100题非常像，那么我们就可以直接修改grid数组来完成，这样一点额外空间都用不到，当然面试的时候可能会不让修改，那就建个数组。因为这里需要用到左侧和上侧的，且需要完成第一行和第一列的布置，因此没法优化空间了。
所以空间要么0要么O(M*N)，看面试官咋选了。
class Solution {
public int minPathSum(int[][] grid) {
//dp
int n = grid.length;
int m = grid[0].length;
//第一行全都加成路径和
for(int i=1;i<m;i++){
grid[0][i]=grid[0][i-1]+grid[0][i];
}
//第一列全都加成路径和
for(int j=1;j<n;j++){
grid[j][0]=grid[j-1][0]+grid[j][0];
}
//开始搞第二行 然后每行接着往下搞
for(int i=1;i<n;i++){
for(int j=1;j<m;j++){
grid[i][j]=Math.min(grid[i][j-1],grid[i-1][j])+grid[i][j];
}
}
return grid[n-1][m-1];
}
}
剑指 Offer II 098. 路径的数目
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
问总共有多少条不同的路径？
示例：
经典暴力解不过class Solution {
int res=0;
int y;
public int uniquePaths(int m, int n) {
//经典暴力
y=n;
help(m-1,0);
return res;
}
public void help(int m, int n) {
if(m==0&&n==y-1){
res++;
return;
}
if(m<0||n>y-1){
return;
}
help(m-1,n);
help(m,n+1);
}
}
dp数组
这类题型已经开始轻车熟路起来了，我的建议是下次直接dp好吧~
分析：这里可以弄一个一样大小的数组，然后每个数都是(0,0)处到(i,j)处的方法数，第一列和第一行是固定都为1，其余的左和上相加即为当前处的可到达方法数。
思路：让第一列和第一行都是1 然后每个其他元素左和上加起来 一行一行的加，一直到右下角，右下角即为结果。
class Solution {
public int uniquePaths(int m, int n) {
//经典dp
int[][] res=new int[m][n];
//第一列全都为1
for(int i=0;i<m;i++){
res[i][0]=1;
}
//第一行全都为1
for(int i=1;i<n;i++){
res[0][i]=1;
}
//开始搞第二行 然后每行接着往下搞
for(int i=1;i<m;i++){
for(int j=1;j<n;j++){
res[i][j]=res[i-1][j]+res[i][j-1];
}
}
return res[m-1][n-1];
}
}
好像也没法优化(错！ 可以优化 只要是这一行数据仅与上一行和这一行的内容有关，即可优化成左脚踩右脚)
但是优化的代码很简单，就不写了捏。
97是个困难，害怕 先挑中等的写,这里先写89是因为第90题是89的加强版。
剑指 Offer II 089. 房屋偷盗一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响小偷偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组 nums ，请计算 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
暴力不过class Solution {
int max=Integer.MIN_VALUE;
public int rob(int[] nums) {
if(nums.length==1){
return nums[0];
}
//这里也需要两个分支
help0(nums,0,0);
help0(nums,1,0);
return max;
}
public void help0(int[] nums,int i,int res) {
//我们i+1的位置不让走 我们可以走i+2,i+3的位置，而i+4的时候可以通过走
//i+2再走i+4 必定是单走一个i+4大，因此我们只需要走两个分支
if(i>nums.length-1){
max=Math.max(max,res);
return ;
}
if(i==nums.length-2){
max=Math.max(max,res+nums[i]);
return ;
}
if(i==nums.length-1){
max=Math.max(max,res+nums[i]);
return ;
}
help0(nums,i+2,res+nums[i]);
help0(nums,i+3,res+nums[i]);
}
}
dp1:我自己的思路
从第90题回来，还是看官方的题解吧，折磨
我自己的思路：先搞出来前三个点，第一二个点和原来一样，第三个点是第一个点和第三个点的和。这样前三个点每个点都是当前的最大值，第四个点i只需要比较i-2和i-3位置上哪个更大，更大的加上自己的值就是当前点能偷到的最多的钱。
这里感觉很像路径和的翻版，处理起来稍微复杂，启发的点在于从最后一个点往前推，经典自下而上的去推，去找规律。然后再自上而下的去根据规律获得值。
这个思路对比起来，也是有逻辑的，逻辑就是你去获取当前位置的最好的值，因此无法考虑i-1，得去看i-2和i-3中最大的，把每个结果都认为是结尾处的值。
class Solution {
public int rob(int[] nums) {
//观察这个数组就是一行，我们直接遍历两边这个数组也能得到结果
//通过数组去维护每个房屋的最大的偷的金额
//前三个数是固定住的 后面每个数是i-2和i-3中的更大的值
int n=nums.length;
if(n==1){return nums[0];}
if(n==2){return Math.max(nums[0],nums[1]);}
if(n==3){return Math.max(nums[0]+nums[2],nums[1]);}
nums[2]=nums[0]+nums[2];
for(int i=3;i<n;i++){
nums[i]=Math.max(nums[i-2],nums[i-3])+nums[i];
}
return Math.max(nums[n-1],nums[n-2]);
}
}
dp2:官方题解的思路
这里用到的是类似于分支的路径选择，前两个点处理一样，从第三个点开始视为k，衍生出两种情况：
- 偷第k间，就是前k-2间最高的金额+第k间金额。
- 不偷第k间，就是前k-1间最高的金额。
这样写出的代码：
class Solution {
public int rob(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
int length = nums.length;
if (length == 1) {
return nums[0];
}
int[] dp = new int[length];
dp[0] = nums[0];
//这个很关键嗷 每次第二个点都应当是最大的那个
dp[1] = Math.max(nums[0], nums[1]);
for (int i = 2; i < length; i++) {
dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]);
}
return dp[length - 1];
}
}
这个思路对比起来，是放弃了一定的思考，因为没有dp[i-1]会一直更大(这里很难理解，感觉看官方更清晰一些)，因此合理。感觉它的思路来源是从前往后走推出来的，因此更便于理解。
dp3:滚动数组优化空间官方解因为只关心前两个和，就可以只保存两个值，first和second。
class Solution {
public int rob(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
int length = nums.length;
if (length == 1) {
return nums[0];
}
int first = nums[0], second = Math.max(nums[0], nums[1]);
for (int i = 2; i < length; i++) {
int temp = second;
second = Math.max(first + nums[i], second);
first = temp;
}
return second;
}
}
而我自己的话，需要搞一个长度为4的数组，一直滚动着走，大概会用到%那种，就不写了。
剑指 Offer II 090. 环形房屋偷盗一个专业的小偷，计划偷窃一个环形街道上沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。
给定一个代表每个房屋存放金额的非负整数数组 nums ，请计算 在不触动警报装置的情况下 ，今晚能够偷窃到的最高金额。
这个题和89题就多了个环，所以我们抽象成一个函数，限定出两个范围，0-n-2和1-n-1这两个范围，分别取最大值并求最大值返回。
class Solution {
public int rob(int[] nums) {
int n=nums.length;
if(n==1){
return nums[0];
}
if(n==2){
return Math.max(nums[0], nums[1]);
}
return Math.max(help(nums,0,n-2),help(nums,1,n-1));
}
//找范围内的最大值
public int help(int[] nums,int start,int end) {
int first = nums[start];
//这个第二个数 必定是最大值
int second=Math.max(nums[start],nums[start+1]);
for(int i=start+2;i<=end;i++){
//左脚踩右脚
int temp = second;
second=Math.max(second,first+nums[i]);
first = temp;
}
return second;
}
}
总结
- 把89题抽象成函数，经历了一顿毒打 我想我应该已经背过了2和3
- 第二个数是前两个数的最大值
- 状态转移方程：res[i]=max(res[i-1],res[i-2]+nums[i])
- 可以左脚踩右脚来优化空间
假如有一排房子，共 n 个，每个房子可以被粉刷成红色、蓝色或者绿色这三种颜色中的一种，你需要粉刷所有的房子并且使其相邻的两个房子颜色不能相同。
当然，因为市场上不同颜色油漆的价格不同，所以房子粉刷成不同颜色的花费成本也是不同的。每个房子粉刷成不同颜色的花费是以一个 n x 3 的正整数矩阵 costs 来表示的。
例如，costs[0][0] 表示第 0 号房子粉刷成红色的成本花费；costs[1][2] 表示第 1 号房子粉刷成绿色的花费，以此类推。
请计算出粉刷完所有房子最少的花费成本。
dp一眼丁真就第一行是初始状态三个数，第二行往后，每个都调上一行的非自己列的最小的数即可，因为只有两个行硬相关所有可以直接优化。
咋找出来的呢，感觉这个规律比较明显，比上两道简单多了。
class Solution {
public int minCost(int[][] costs) {
int n=costs.length;
int[][] res = new int[n][3];
res[0][0]=costs[0][0];
res[0][1]=costs[0][1];
res[0][2]=costs[0][2];
for(int i=1;i<n;i++){
costs[i][0]=Math.min(costs[i-1][1],costs[i-1][2])+costs[i][0];
costs[i][1]=Math.min(costs[i-1][0],costs[i-1][2])+costs[i][1];
costs[i][2]=Math.min(costs[i-1][0],costs[i-1][1])+costs[i][2];
}
return Math.min(costs[n-1][0],Math.min(costs[n-1][2],costs[n-1][1]));
}
}
空间优化
两行，左脚踩右脚，O(1)的空间复杂度。
class Solution {
public int minCost(int[][] costs) {
int n=costs.length;
int[] a = new int[3];
int[] b = new int[3];
a[0]=costs[0][0];
a[1]=costs[0][1];
a[2]=costs[0][2];
int[] c;
for(int i=1;i<n;i++){
b[0]=Math.min(a[1],a[2])+costs[i][0];
b[1]=Math.min(a[0],a[2])+costs[i][1];
b[2]=Math.min(a[1],a[0])+costs[i][2];
c=b;
b=a;
a=c;
}
return Math.min(a[0],Math.min(a[2],a[1]));
}
}
剑指 Offer II 092. 翻转字符
如果一个由 '0' 和 '1' 组成的字符串，是以一些 '0'（可能没有 '0'）后面跟着一些 '1'（也可能没有 '1'）的形式组成的，那么该字符串是 单调递增 的。
我们给出一个由字符 '0' 和 '1' 组成的字符串 s，我们可以将任何 '0' 翻转为 '1' 或者将 '1' 翻转为 '0'。
返回使 s 单调递增 的最小翻转次数。
dp O(N)这个题折磨了我好久，因为和平时的dp不一样，当然最后看起来很简单。。。。需要用到两行的空间。原理在注释里差不多全了。
这里记录下思路：根据已有序列去推下一位应该最小为多少，0的前面只能有0，因此无论怎么翻转都是0那一行的事，如果当前为1就吧前一位+1是这一位，如果是0就直接等于前一位。1的前面可以是0也可以是1，因此我们可以去dp数组中上一位最小的值放到这里。
class Solution {
public int minFlipsMonoIncr(String s) {
int n=s.length();
//[i][0]记录字符串s在i位置上，字符为0时的最小翻转次数
//[i][1]记录字符串s在i位置上，字符为1时的最小翻转次数
int[][] res = new int[n][2];
if(s.charAt(0)=='1'){
res[0][0]=1;
}else{
res[0][1]=1;
}
for(int i=1;i<n;i++){
if(s.charAt(i)=='0'){
//0的前面只能是0 所以需要加上上一个值和当前是否为0
res[i][0]=res[i-1][0];
//而1的时候 前面可以是0也可以是1 找到最小即可
res[i][1]=Math.min(res[i-1][0],res[i-1][1])+1;
}else{
res[i][0]=res[i-1][0]+1;
res[i][1]=Math.min(res[i-1][0],res[i-1][1]);
}
}
return Math.min(res[n-1][0],res[n-1][1]);
}
}
dp空间优化 O(1)
每个都只与前一个数有关，所以其实只保留两个数即可。
class Solution {
public int minFlipsMonoIncr(String s) {
int n=s.length();
int a=0,b=0;//a记录0那一行的最新 b记录1那一行的最新
if(s.charAt(0)=='1'){
a=1;
}else{
b=1;
}
for(int i=1;i<n;i++){
if(s.charAt(i)=='0'){
//a不需要变化。。
//而1的时候 前面可以是0也可以是1 找到最小即可
b=Math.min(a,b)+1;
}else{
b=Math.min(a,b);
a=a+1;
}
}
return Math.min(a,b);
}
}
总结
看起来只需要找出状态转移方程就能轻松解决问题，找不出来就寄了。多去分析问题本身，用实验的方法往前推进。
剑指 Offer II 093. 最长斐波那契数列(2022.7.3)如果序列 X_1, X_2, ..., X_n 满足下列条件，就说它是 斐波那契式 的：
-
n >= 3
-
对于所有 i + 2 <= n，都有 X_i + X_{i+1} = X_{i+2}
给定一个严格递增的正整数数组形成序列 arr ，找到 arr 中最长的斐波那契式的子序列的长度。如果一个不存在，返回 0 。
（回想一下，子序列是从原序列 arr 中派生出来的，它从 arr 中删掉任意数量的元素（也可以不删），而不改变其余元素的顺序。例如， [3, 5, 8] 是 [3, 4, 5, 6, 7, 8] 的一个子序列）
暴力不过 O(N3)一点优化没有，直接三次方
class Solution {
public int lenLongestFibSubseq(int[] arr) {
int n=arr.length;
int res = 0;
for(int i=0;i<n-2;i++){
for(int j=i+1;j<n-1;j++){
int a = arr[i];
int b = arr[j];//记录前两个数
int len=2;//记录长度
for(int z=j+1;z<n;z++){
if(arr[z]==(a+b)){
len++;
a=b;
b=arr[z];
}
}
res=Math.max(res,len);
}
}
return res==2?0:res;
}
}
3个for的dp 还是O(N3)
class Solution {
public int lenLongestFibSubseq(int[] arr) {
int n=arr.length;
int res = 0;
int[][] dp = new int[n][n];
for(int i=0;i<n-2;i++){
for(int j=i+1;j<n-1;j++){
int a = arr[i];
int b = arr[j];//记录前两个数
for(int z=j+1;z<n;z++){
if(arr[z]==(a+b)){
dp[j][z]=dp[i][j]+1;
res=Math.max(res,dp[j][z]);
}
}
}
}
return res==0?0:res+2;
}
}
根据Map减少一个for O(N2)
class Solution {
public int lenLongestFibSubseq(int[] arr) {
int n=arr.length;
int res = 0;
int[][] dp = new int[n][n];
HashMap<Integer,Integer> map = new HashMap<>();
for(int x=0;x<n;x++){
map.put(arr[x],x);
}
for(int i=0;i<n-2;i++){
for(int j=i+1;j<n-1;j++){
int z = map.getOrDefault(arr[i]+arr[j],-1);
if(z!=-1){
dp[j][z]=dp[i][j]+1;
res=Math.max(res,dp[j][z]);
}
}
}
return res==0?0:res+2;
}
}
dp➕双指针 最优解法 接近O(NlogN)
class Solution {
public int lenLongestFibSubseq(int[] arr) {
int n=arr.length;
int res = 0;
int[][] dp = new int[n][n];
for(int i=2;i<n;i++){
int a=0,b=n-1;
while(a<b){
int sum = arr[a]+arr[b];
if(arr[i]==sum){
dp[b][i]=dp[a][b]+1;
res=Math.max(res,dp[b][i]);
a++;b--;
}else if(arr[i]>sum){
a++;
}else{
b--;
}
}
}
return res==0?0:res+2;
}
}
总结
感觉这种题目，先定义dp数组的意义，最后两个数是最大的，从前面最小的0开始往后加。
然后利用for循环写出基础思路，然后用map，我觉得一般是做到这个程度。
双指针的这个，有点类似三数之和那种，归结为两个数的和并且利用顺序递增的规律完成(类似荷兰国旗)。
剑指 Offer II 086. 分割回文子字符串给定一个字符串 s ，请将 s 分割成一些子串，使每个子串都是 回文串 ，返回 s 所有可能的分割方案。
回文串 是正着读和反着读都一样的字符串。
回溯+dpclass Solution {
boolean[][] f;
List<List<String>> tmp = new ArrayList<List<String>>();
List<String> ans = new ArrayList<String>();
int n;
public String[][] partition(String s) {
n = s.length();
f = new boolean[n][n];
for (int i = 0; i < n; ++i) {
Arrays.fill(f[i], true);
}
for (int i = n - 1; i >= 0; --i) {
for (int j = i + 1; j < n; ++j) {
f[i][j] = (s.charAt(i) == s.charAt(j)) && f[i + 1][j - 1];
}
}
dfs(s, 0);
int rows = tmp.size();
String[][] ret = new String[rows][];
for (int i = 0; i < rows; ++i) {
ret[i] = tmp.get(i).toArray(new String[tmp.get(i).size()]);
}
return ret;
}
public void dfs(String s, int i) {
if (i == n) {
tmp.add(new ArrayList<String>(ans));
return;
}
for (int j = i; j < n; ++j) {
if (f[i][j]) {
ans.add(s.substring(i, j + 1));
dfs(s, j + 1);
ans.remove(ans.size() - 1);
}
}
}
}
这个题首先是关于回文的，因此可以用上dp来判断是否是回文字符串。方程就是看s[i]s[j]&&dp是否为真，且ij以及i<j的二维表的字段都是真，因为代表一个字符的串和空串。这里dp的内容就解决了，"google"的dp表格如下。
下面是回溯的内容，第一次接触到这个。大致可以归纳总结为两个循环，首先是外层的循环，用i来控制行，从0开始往下走，j用来控制列。
举例：假设输入的为"google"，先从(0,0)这一行往后走，由于(0,0)为真，添加g至ans，走到(1,1)为真，添加o至ans，依次走，直到走到最后(6,6)，ans为，这样添加到tmp中第一个结果。
然后开始回溯return，第一步回溯到(5,5)，删掉"e"，回到(4,4)，删掉"l"，j继续往后走(4,5)，发现都为false，就继续回溯。走到(3,3)删掉"g"，然后(3,4)(3,5)都为false；以此类推回到(1,1)，删掉"o"，此时ans中只有，开始走(1,2)(1,5)因为(1,2)为真，加入"oo"，我们继续添加(3,3)、(4,4)、(5,5)，就完成了第二结果；继续回溯，走到(0,3)时候发现"goog"为开头的，继续加入(4,4)、(5,5)得到第三个结果，我们返回最终结果。
我们可以看到，每一种字符串组合方法(O(2N))，下面的每个字符可能都要走到(O(N2)，因此时间复杂度为O(2N*N2)，回溯的精髓在于，保存已有情况，继续遍历下面的可能情况，一进一出来不断递归新的可能。
i作为行是通过用系统栈去记住的，j每次去遍历每一列的可能性，如果这一列为True，直接存入(i,j)的字符串，并且i跳到第j+1行。
这是我接触的第一个回溯题目，感觉很猛，自己完全想不出来那种。。。后面还要多加努力。
本文共计7756个文字，预计阅读时间需要32分钟。
剑指 Offer II 100：三角形中最小路径之和 + 给定一个三角形 triangle，找出从顶部到底部的最小路径和。每一步只能移动到下一行中相邻的结点上。相邻的结点在这里指的是在同一行上、左或右紧挨着的结点。
剑指 Offer II 100：三角形中最小路径之和给定一个三角形 triangle ，找出自顶向下的最小路径和。
每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。也就是说，如果正位于当前行的下标 i ，那么下一步可以移动到下一行的下标 i 或 i + 1 。
示例 1：
输入：triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
输出：11
解释：如下面简图所示：
2
3 4
6 5 7
4 1 8 3
自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。示例 2：
示例2：
输入：triangle = [[-10]]
输出：-10
提示：
- 1 <= triangle.length <= 200
- triangle[0].length == 1
- triangle[i].length == triangle[i - 1].length + 1
- -104 <= triangle[i][j] <= 104
就直接递归所有的可能 去获得最小的那个 很明显过不了最后一个用例。
class Solution {
int min = Integer.MAX_VALUE;
public int minimumTotal(List<List<Integer>> triangle) {
if(triangle.size()==1){
return triangle.get(0).get(0);
}
getRES(triangle,1,0,triangle.get(0).get(0));//第0层 第0个 前面路线的和为0
return min;
}
public void getRES(List<List<Integer>> triangle,int level,int index,int res){
if(level==triangle.size()-1){
min=Math.min(min,Math.min(triangle.get(level).get(index)+res,triangle.get(level).get(index+1)+res));
return;
}
getRES(triangle,level+1,index,res+triangle.get(level).get(index));
getRES(triangle,level+1,index+1,res+triangle.get(level).get(index+1));
}
}
这里我模糊的记忆告诉我优化需要根据输入的维数，而我的输入有4个，数组、遍历的层数(到第几层了)、当前索引到多少了、和是多少。
我就以为需要搞个四维的东西，其实不然，我们可以直接通过建立一个相同大小的二维数组，根据这个可以保存之前走过的值，而不是通过系统栈的递归重复去进行计算，有点像斐波那契数列的空间保存优化。
这里就有了我们的解法二：通过dp数组优化。
解法二：dp数组 空间O(N2)我们每次通过数组记录我们之前的选择。首先自下而上（这个思路很重要，斐波那契数列问题也是这样优化的）的去思考，会发现每个位置(假设为i)都只能从上一层的该位置或者i-1位置过来，而且这条路径一定会加上当前层i位置值，我们只需要从上一层的这两个数中挑选较小的即可。
class Solution {
public int minimumTotal(List<List<Integer>> triangle) {
if(triangle.size()==1){
return triangle.get(0).get(0);
}
//经典dp做法 因为当前行的大小可以根据上一行中对应位置的元素得到
//用i j表示横纵坐标，每一行j<=i 把数字向左对齐是一个等腰直角三角形
//但是当处于每行中的0位置和最右位置时，数据可以直接得出 即上一行最左侧的路径和和最右侧的路径和
//其余的时候得判断一下两个中的较小值
int n = triangle.size();
int[][] res = new int[n][n];
int i=0,j=0;
res[0][0] = triangle.get(0).get(0);
for(i=1;i<n;i++){//从1开始遍历 因为(0,0)的路径和就是自己
//每一行0处的公式：res(i,0)=res(i-1,0)+triangle(i,0)
res[i][0]=res[i-1][0]+triangle.get(i).get(0);
for(j=1;j<i;j++){//这里是小于i 因为等于i的要特殊判定
//在第二行的时候 直接跳过这里了，因此从第三行才开始执行这个循环
res[i][j]=Math.min(res[i-1][j-1],res[i-1][j])+triangle.get(i).get(j);
}
//每一行i处的公式：res(i,i)=res(i-1,i-1)+triangle(i,i)
res[i][i]=res[i-1][i-1]+triangle.get(i).get(i);
}
int min = res[n-1][0];
for(i=1;i<n;i++){
min=Math.min(min,res[n-1][i]);
}
return min;
}
}
解法三：优化dp数组至空间O(N)
这里我们观察数组可以意识到，我们数据与数据之间只有上下一行有关系，因此我们有了优化做法，用两个长度为n的数组，左脚踩右脚完成所有路径和的叠加。(这里我们可以意识到，每个路径都需要走到最下面的一层，因此每个路径是可以自下而上的去探索规律的)。
class Solution {
public int minimumTotal(List<List<Integer>> triangle) {
if(triangle.size()==1){
return triangle.get(0).get(0);
}
//优化做法 用两个长度为n的数组 左脚踩右脚完成
int n = triangle.size();
int[] a = new int[n];
int[] b = new int[n];
int i=0,j=0;
a[0] = triangle.get(0).get(0);//a永远是旧的那个
for(i=1;i<n;i++){//b永远是新的那一个行
//每一行0处的公式：b(0)=a(0)+triangle(i,0)
b[0]=a[0]+triangle.get(i).get(0);
for(j=1;j<i;j++){//这里是小于i 因为等于i的要特殊判定
//在第二行的时候 直接跳过这里了，因此从第三行才开始执行这个循环
b[j]=Math.min(a[j-1],a[j])+triangle.get(i).get(j);
}
//每一行i处的公式：res(i,i)=res(i-1,i-1)+triangle(i,i)
b[i]=a[i-1]+triangle.get(i).get(i);
//交换a和b的指向
int[] c = a;
a=b;
b=c;
}
//因为最后的交换 现在a是结果行
int min = a[0];
for(i=1;i<n;i++){
min=Math.min(min,a[i]);
}
return min;
}
}
这里的数组是用到了两个长度为N的数组，a和b。那么我们能不能继续进行优化呢？答案当然是可以的，我们可以只用一个数组就完成遍历，这就是解法四。
解法四：一个数组完成我们前几种方法的遍历，是通过每一行从左到右去生成下一行的内容，这样我们每个数据会依赖上一个行的上侧和左侧。那么我们换一种思路去遍历，从右至左的遍历，又可以剩下一个数组的空间：
每个数据只依赖上一行的上和左，我们将所有数据在一行上更新的话，从右往左走，每次最右侧的数据只依赖上一行的最右侧，每新的一行都要比上一行多一个，那么最右侧的i位置，只依赖上一行的i-1位置，即左侧的值。而右侧第二个数i-1位置，依赖上和左，而上就是当前i-1位置的值，左是i-2位置的值，从而我们可以更新i-1位置的值。
因此，我们可以通过一个数组去完成这个任务。
class Solution {
public int minimumTotal(List<List<Integer>> triangle) {
if(triangle.size()==1){
return triangle.get(0).get(0);
}
//优化做法 用一个长度为n的数组 从右到左遍历完成
int n = triangle.size();
int[] res = new int[n];
int i=0,j=0;
res[0] = triangle.get(0).get(0);
for(i=1;i<n;i++){
//i不变 还是从上往下遍历 j需要从最大往最小遍历即从右到左
//因此需要先把i位置的值搞上 最后搞0位置的值
res[i]=res[i-1]+triangle.get(i).get(i);
for(j=i-1;j>0;j--){
res[j]=Math.min(res[j-1],res[j])+triangle.get(i).get(j);
}
res[0]=res[0]+triangle.get(i).get(0);
}
int min = res[0];
for(i=1;i<n;i++){
min=Math.min(min,res[i]);
}
return min;
}
}
总结
- 要学会自下而上的思考方式，根据这个再从上往下走。
- 学到了dp的优化，去找数据之间的依赖关系。
- 根据依赖关系再去进行空间的优化。
- 多去尝试遍历方式能否继续优化，对空间的利用可以做到极致。
给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
说明：一个机器人每次只能向下或者向右移动一步。
示例 1：
输入：grid = [[1,3,1],[1,5,1],[4,2,1]]
输出：7
解释：因为路径 1→3→1→1→1 的总和最小。
示例 2：
输入：grid = [[1,2,3],[4,5,6]]
输出：12
提示：
- m == grid.length
- n == grid[i].length
- 1 <= m, n <= 200
- 0 <= grid[i][j] <= 100
注意：本题与主站 64 题相同： leetcode-cn.com/problems/minimum-path-sum/
解法一：暴力解老规矩，先试试暴力解法。
class Solution {
int min = Integer.MAX_VALUE;
public int minPathSum(int[][] grid) {
//暴力解
help(grid,0,0,0);
return min;
}
public void help(int[][] grid,int i,int j,int res) {
if((i==grid.length-1)&&(j==grid[0].length-1)){
res+=grid[grid.length-1][grid[0].length-1];
min=Math.min(min,res);
return;
}
if(i>grid.length-1||j>grid[0].length-1){
return;
}
help(grid,i+1,j,res+grid[i][j]);
help(grid,i,j+1,res+grid[i][j]);
}
}
经典不给过嗷，现在去想咋用dp去做优化。
解法二：dp数组这里我们直接一步到位，先分析这个问题，主要还是搞路径和对吧，那么我们就可以给中间状态的每一步去记录下来，就想到了用一个一样大小的数组去记录。首先是第一行和第一列的路径和是固定的，只能这么走（因为规定了是最短路径，且方格中每个数都大于0，那么每多走一步都会浪费，在边上的相邻的两个数肯定是直接走是最近的）。
因此我们可以先把第一行和第一列的结果求出来。然后挨个去求每一行的路径和，每个地方只需要去判断左和上哪个更小，哪个更小就加到自己就形成了最小的当前路径和，和第100题非常像，那么我们就可以直接修改grid数组来完成，这样一点额外空间都用不到，当然面试的时候可能会不让修改，那就建个数组。因为这里需要用到左侧和上侧的，且需要完成第一行和第一列的布置，因此没法优化空间了。
所以空间要么0要么O(M*N)，看面试官咋选了。
class Solution {
public int minPathSum(int[][] grid) {
//dp
int n = grid.length;
int m = grid[0].length;
//第一行全都加成路径和
for(int i=1;i<m;i++){
grid[0][i]=grid[0][i-1]+grid[0][i];
}
//第一列全都加成路径和
for(int j=1;j<n;j++){
grid[j][0]=grid[j-1][0]+grid[j][0];
}
//开始搞第二行 然后每行接着往下搞
for(int i=1;i<n;i++){
for(int j=1;j<m;j++){
grid[i][j]=Math.min(grid[i][j-1],grid[i-1][j])+grid[i][j];
}
}
return grid[n-1][m-1];
}
}
剑指 Offer II 098. 路径的数目
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
问总共有多少条不同的路径？
示例：
经典暴力解不过class Solution {
int res=0;
int y;
public int uniquePaths(int m, int n) {
//经典暴力
y=n;
help(m-1,0);
return res;
}
public void help(int m, int n) {
if(m==0&&n==y-1){
res++;
return;
}
if(m<0||n>y-1){
return;
}
help(m-1,n);
help(m,n+1);
}
}
dp数组
这类题型已经开始轻车熟路起来了，我的建议是下次直接dp好吧~
分析：这里可以弄一个一样大小的数组，然后每个数都是(0,0)处到(i,j)处的方法数，第一列和第一行是固定都为1，其余的左和上相加即为当前处的可到达方法数。
思路：让第一列和第一行都是1 然后每个其他元素左和上加起来 一行一行的加，一直到右下角，右下角即为结果。
class Solution {
public int uniquePaths(int m, int n) {
//经典dp
int[][] res=new int[m][n];
//第一列全都为1
for(int i=0;i<m;i++){
res[i][0]=1;
}
//第一行全都为1
for(int i=1;i<n;i++){
res[0][i]=1;
}
//开始搞第二行 然后每行接着往下搞
for(int i=1;i<m;i++){
for(int j=1;j<n;j++){
res[i][j]=res[i-1][j]+res[i][j-1];
}
}
return res[m-1][n-1];
}
}
好像也没法优化(错！ 可以优化 只要是这一行数据仅与上一行和这一行的内容有关，即可优化成左脚踩右脚)
但是优化的代码很简单，就不写了捏。
97是个困难，害怕 先挑中等的写,这里先写89是因为第90题是89的加强版。
剑指 Offer II 089. 房屋偷盗一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响小偷偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组 nums ，请计算 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
暴力不过class Solution {
int max=Integer.MIN_VALUE;
public int rob(int[] nums) {
if(nums.length==1){
return nums[0];
}
//这里也需要两个分支
help0(nums,0,0);
help0(nums,1,0);
return max;
}
public void help0(int[] nums,int i,int res) {
//我们i+1的位置不让走 我们可以走i+2,i+3的位置，而i+4的时候可以通过走
//i+2再走i+4 必定是单走一个i+4大，因此我们只需要走两个分支
if(i>nums.length-1){
max=Math.max(max,res);
return ;
}
if(i==nums.length-2){
max=Math.max(max,res+nums[i]);
return ;
}
if(i==nums.length-1){
max=Math.max(max,res+nums[i]);
return ;
}
help0(nums,i+2,res+nums[i]);
help0(nums,i+3,res+nums[i]);
}
}
dp1:我自己的思路
从第90题回来，还是看官方的题解吧，折磨
我自己的思路：先搞出来前三个点，第一二个点和原来一样，第三个点是第一个点和第三个点的和。这样前三个点每个点都是当前的最大值，第四个点i只需要比较i-2和i-3位置上哪个更大，更大的加上自己的值就是当前点能偷到的最多的钱。
这里感觉很像路径和的翻版，处理起来稍微复杂，启发的点在于从最后一个点往前推，经典自下而上的去推，去找规律。然后再自上而下的去根据规律获得值。
这个思路对比起来，也是有逻辑的，逻辑就是你去获取当前位置的最好的值，因此无法考虑i-1，得去看i-2和i-3中最大的，把每个结果都认为是结尾处的值。
class Solution {
public int rob(int[] nums) {
//观察这个数组就是一行，我们直接遍历两边这个数组也能得到结果
//通过数组去维护每个房屋的最大的偷的金额
//前三个数是固定住的 后面每个数是i-2和i-3中的更大的值
int n=nums.length;
if(n==1){return nums[0];}
if(n==2){return Math.max(nums[0],nums[1]);}
if(n==3){return Math.max(nums[0]+nums[2],nums[1]);}
nums[2]=nums[0]+nums[2];
for(int i=3;i<n;i++){
nums[i]=Math.max(nums[i-2],nums[i-3])+nums[i];
}
return Math.max(nums[n-1],nums[n-2]);
}
}
dp2:官方题解的思路
这里用到的是类似于分支的路径选择，前两个点处理一样，从第三个点开始视为k，衍生出两种情况：
- 偷第k间，就是前k-2间最高的金额+第k间金额。
- 不偷第k间，就是前k-1间最高的金额。
这样写出的代码：
class Solution {
public int rob(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
int length = nums.length;
if (length == 1) {
return nums[0];
}
int[] dp = new int[length];
dp[0] = nums[0];
//这个很关键嗷 每次第二个点都应当是最大的那个
dp[1] = Math.max(nums[0], nums[1]);
for (int i = 2; i < length; i++) {
dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]);
}
return dp[length - 1];
}
}
这个思路对比起来，是放弃了一定的思考，因为没有dp[i-1]会一直更大(这里很难理解，感觉看官方更清晰一些)，因此合理。感觉它的思路来源是从前往后走推出来的，因此更便于理解。
dp3:滚动数组优化空间官方解因为只关心前两个和，就可以只保存两个值，first和second。
class Solution {
public int rob(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
int length = nums.length;
if (length == 1) {
return nums[0];
}
int first = nums[0], second = Math.max(nums[0], nums[1]);
for (int i = 2; i < length; i++) {
int temp = second;
second = Math.max(first + nums[i], second);
first = temp;
}
return second;
}
}
而我自己的话，需要搞一个长度为4的数组，一直滚动着走，大概会用到%那种，就不写了。
剑指 Offer II 090. 环形房屋偷盗一个专业的小偷，计划偷窃一个环形街道上沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。
给定一个代表每个房屋存放金额的非负整数数组 nums ，请计算 在不触动警报装置的情况下 ，今晚能够偷窃到的最高金额。
这个题和89题就多了个环，所以我们抽象成一个函数，限定出两个范围，0-n-2和1-n-1这两个范围，分别取最大值并求最大值返回。
class Solution {
public int rob(int[] nums) {
int n=nums.length;
if(n==1){
return nums[0];
}
if(n==2){
return Math.max(nums[0], nums[1]);
}
return Math.max(help(nums,0,n-2),help(nums,1,n-1));
}
//找范围内的最大值
public int help(int[] nums,int start,int end) {
int first = nums[start];
//这个第二个数 必定是最大值
int second=Math.max(nums[start],nums[start+1]);
for(int i=start+2;i<=end;i++){
//左脚踩右脚
int temp = second;
second=Math.max(second,first+nums[i]);
first = temp;
}
return second;
}
}
总结
- 把89题抽象成函数，经历了一顿毒打 我想我应该已经背过了2和3
- 第二个数是前两个数的最大值
- 状态转移方程：res[i]=max(res[i-1],res[i-2]+nums[i])
- 可以左脚踩右脚来优化空间
假如有一排房子，共 n 个，每个房子可以被粉刷成红色、蓝色或者绿色这三种颜色中的一种，你需要粉刷所有的房子并且使其相邻的两个房子颜色不能相同。
当然，因为市场上不同颜色油漆的价格不同，所以房子粉刷成不同颜色的花费成本也是不同的。每个房子粉刷成不同颜色的花费是以一个 n x 3 的正整数矩阵 costs 来表示的。
例如，costs[0][0] 表示第 0 号房子粉刷成红色的成本花费；costs[1][2] 表示第 1 号房子粉刷成绿色的花费，以此类推。
请计算出粉刷完所有房子最少的花费成本。
dp一眼丁真就第一行是初始状态三个数，第二行往后，每个都调上一行的非自己列的最小的数即可，因为只有两个行硬相关所有可以直接优化。
咋找出来的呢，感觉这个规律比较明显，比上两道简单多了。
class Solution {
public int minCost(int[][] costs) {
int n=costs.length;
int[][] res = new int[n][3];
res[0][0]=costs[0][0];
res[0][1]=costs[0][1];
res[0][2]=costs[0][2];
for(int i=1;i<n;i++){
costs[i][0]=Math.min(costs[i-1][1],costs[i-1][2])+costs[i][0];
costs[i][1]=Math.min(costs[i-1][0],costs[i-1][2])+costs[i][1];
costs[i][2]=Math.min(costs[i-1][0],costs[i-1][1])+costs[i][2];
}
return Math.min(costs[n-1][0],Math.min(costs[n-1][2],costs[n-1][1]));
}
}
空间优化
两行，左脚踩右脚，O(1)的空间复杂度。
class Solution {
public int minCost(int[][] costs) {
int n=costs.length;
int[] a = new int[3];
int[] b = new int[3];
a[0]=costs[0][0];
a[1]=costs[0][1];
a[2]=costs[0][2];
int[] c;
for(int i=1;i<n;i++){
b[0]=Math.min(a[1],a[2])+costs[i][0];
b[1]=Math.min(a[0],a[2])+costs[i][1];
b[2]=Math.min(a[1],a[0])+costs[i][2];
c=b;
b=a;
a=c;
}
return Math.min(a[0],Math.min(a[2],a[1]));
}
}
剑指 Offer II 092. 翻转字符
如果一个由 '0' 和 '1' 组成的字符串，是以一些 '0'（可能没有 '0'）后面跟着一些 '1'（也可能没有 '1'）的形式组成的，那么该字符串是 单调递增 的。
我们给出一个由字符 '0' 和 '1' 组成的字符串 s，我们可以将任何 '0' 翻转为 '1' 或者将 '1' 翻转为 '0'。
返回使 s 单调递增 的最小翻转次数。
dp O(N)这个题折磨了我好久，因为和平时的dp不一样，当然最后看起来很简单。。。。需要用到两行的空间。原理在注释里差不多全了。
这里记录下思路：根据已有序列去推下一位应该最小为多少，0的前面只能有0，因此无论怎么翻转都是0那一行的事，如果当前为1就吧前一位+1是这一位，如果是0就直接等于前一位。1的前面可以是0也可以是1，因此我们可以去dp数组中上一位最小的值放到这里。
class Solution {
public int minFlipsMonoIncr(String s) {
int n=s.length();
//[i][0]记录字符串s在i位置上，字符为0时的最小翻转次数
//[i][1]记录字符串s在i位置上，字符为1时的最小翻转次数
int[][] res = new int[n][2];
if(s.charAt(0)=='1'){
res[0][0]=1;
}else{
res[0][1]=1;
}
for(int i=1;i<n;i++){
if(s.charAt(i)=='0'){
//0的前面只能是0 所以需要加上上一个值和当前是否为0
res[i][0]=res[i-1][0];
//而1的时候 前面可以是0也可以是1 找到最小即可
res[i][1]=Math.min(res[i-1][0],res[i-1][1])+1;
}else{
res[i][0]=res[i-1][0]+1;
res[i][1]=Math.min(res[i-1][0],res[i-1][1]);
}
}
return Math.min(res[n-1][0],res[n-1][1]);
}
}
dp空间优化 O(1)
每个都只与前一个数有关，所以其实只保留两个数即可。
class Solution {
public int minFlipsMonoIncr(String s) {
int n=s.length();
int a=0,b=0;//a记录0那一行的最新 b记录1那一行的最新
if(s.charAt(0)=='1'){
a=1;
}else{
b=1;
}
for(int i=1;i<n;i++){
if(s.charAt(i)=='0'){
//a不需要变化。。
//而1的时候 前面可以是0也可以是1 找到最小即可
b=Math.min(a,b)+1;
}else{
b=Math.min(a,b);
a=a+1;
}
}
return Math.min(a,b);
}
}
总结
看起来只需要找出状态转移方程就能轻松解决问题，找不出来就寄了。多去分析问题本身，用实验的方法往前推进。
剑指 Offer II 093. 最长斐波那契数列(2022.7.3)如果序列 X_1, X_2, ..., X_n 满足下列条件，就说它是 斐波那契式 的：
-
n >= 3
-
对于所有 i + 2 <= n，都有 X_i + X_{i+1} = X_{i+2}
给定一个严格递增的正整数数组形成序列 arr ，找到 arr 中最长的斐波那契式的子序列的长度。如果一个不存在，返回 0 。
（回想一下，子序列是从原序列 arr 中派生出来的，它从 arr 中删掉任意数量的元素（也可以不删），而不改变其余元素的顺序。例如， [3, 5, 8] 是 [3, 4, 5, 6, 7, 8] 的一个子序列）
暴力不过 O(N3)一点优化没有，直接三次方
class Solution {
public int lenLongestFibSubseq(int[] arr) {
int n=arr.length;
int res = 0;
for(int i=0;i<n-2;i++){
for(int j=i+1;j<n-1;j++){
int a = arr[i];
int b = arr[j];//记录前两个数
int len=2;//记录长度
for(int z=j+1;z<n;z++){
if(arr[z]==(a+b)){
len++;
a=b;
b=arr[z];
}
}
res=Math.max(res,len);
}
}
return res==2?0:res;
}
}
3个for的dp 还是O(N3)
class Solution {
public int lenLongestFibSubseq(int[] arr) {
int n=arr.length;
int res = 0;
int[][] dp = new int[n][n];
for(int i=0;i<n-2;i++){
for(int j=i+1;j<n-1;j++){
int a = arr[i];
int b = arr[j];//记录前两个数
for(int z=j+1;z<n;z++){
if(arr[z]==(a+b)){
dp[j][z]=dp[i][j]+1;
res=Math.max(res,dp[j][z]);
}
}
}
}
return res==0?0:res+2;
}
}
根据Map减少一个for O(N2)
class Solution {
public int lenLongestFibSubseq(int[] arr) {
int n=arr.length;
int res = 0;
int[][] dp = new int[n][n];
HashMap<Integer,Integer> map = new HashMap<>();
for(int x=0;x<n;x++){
map.put(arr[x],x);
}
for(int i=0;i<n-2;i++){
for(int j=i+1;j<n-1;j++){
int z = map.getOrDefault(arr[i]+arr[j],-1);
if(z!=-1){
dp[j][z]=dp[i][j]+1;
res=Math.max(res,dp[j][z]);
}
}
}
return res==0?0:res+2;
}
}
dp➕双指针 最优解法 接近O(NlogN)
class Solution {
public int lenLongestFibSubseq(int[] arr) {
int n=arr.length;
int res = 0;
int[][] dp = new int[n][n];
for(int i=2;i<n;i++){
int a=0,b=n-1;
while(a<b){
int sum = arr[a]+arr[b];
if(arr[i]==sum){
dp[b][i]=dp[a][b]+1;
res=Math.max(res,dp[b][i]);
a++;b--;
}else if(arr[i]>sum){
a++;
}else{
b--;
}
}
}
return res==0?0:res+2;
}
}
总结
感觉这种题目，先定义dp数组的意义，最后两个数是最大的，从前面最小的0开始往后加。
然后利用for循环写出基础思路，然后用map，我觉得一般是做到这个程度。
双指针的这个，有点类似三数之和那种，归结为两个数的和并且利用顺序递增的规律完成(类似荷兰国旗)。
剑指 Offer II 086. 分割回文子字符串给定一个字符串 s ，请将 s 分割成一些子串，使每个子串都是 回文串 ，返回 s 所有可能的分割方案。
回文串 是正着读和反着读都一样的字符串。
回溯+dpclass Solution {
boolean[][] f;
List<List<String>> tmp = new ArrayList<List<String>>();
List<String> ans = new ArrayList<String>();
int n;
public String[][] partition(String s) {
n = s.length();
f = new boolean[n][n];
for (int i = 0; i < n; ++i) {
Arrays.fill(f[i], true);
}
for (int i = n - 1; i >= 0; --i) {
for (int j = i + 1; j < n; ++j) {
f[i][j] = (s.charAt(i) == s.charAt(j)) && f[i + 1][j - 1];
}
}
dfs(s, 0);
int rows = tmp.size();
String[][] ret = new String[rows][];
for (int i = 0; i < rows; ++i) {
ret[i] = tmp.get(i).toArray(new String[tmp.get(i).size()]);
}
return ret;
}
public void dfs(String s, int i) {
if (i == n) {
tmp.add(new ArrayList<String>(ans));
return;
}
for (int j = i; j < n; ++j) {
if (f[i][j]) {
ans.add(s.substring(i, j + 1));
dfs(s, j + 1);
ans.remove(ans.size() - 1);
}
}
}
}
这个题首先是关于回文的，因此可以用上dp来判断是否是回文字符串。方程就是看s[i]s[j]&&dp是否为真，且ij以及i<j的二维表的字段都是真，因为代表一个字符的串和空串。这里dp的内容就解决了，"google"的dp表格如下。
下面是回溯的内容，第一次接触到这个。大致可以归纳总结为两个循环，首先是外层的循环，用i来控制行，从0开始往下走，j用来控制列。
举例：假设输入的为"google"，先从(0,0)这一行往后走，由于(0,0)为真，添加g至ans，走到(1,1)为真，添加o至ans，依次走，直到走到最后(6,6)，ans为，这样添加到tmp中第一个结果。
然后开始回溯return，第一步回溯到(5,5)，删掉"e"，回到(4,4)，删掉"l"，j继续往后走(4,5)，发现都为false，就继续回溯。走到(3,3)删掉"g"，然后(3,4)(3,5)都为false；以此类推回到(1,1)，删掉"o"，此时ans中只有，开始走(1,2)(1,5)因为(1,2)为真，加入"oo"，我们继续添加(3,3)、(4,4)、(5,5)，就完成了第二结果；继续回溯，走到(0,3)时候发现"goog"为开头的，继续加入(4,4)、(5,5)得到第三个结果，我们返回最终结果。
我们可以看到，每一种字符串组合方法(O(2N))，下面的每个字符可能都要走到(O(N2)，因此时间复杂度为O(2N*N2)，回溯的精髓在于，保存已有情况，继续遍历下面的可能情况，一进一出来不断递归新的可能。
i作为行是通过用系统栈去记住的，j每次去遍历每一列的可能性，如果这一列为True，直接存入(i,j)的字符串，并且i跳到第j+1行。
这是我接触的第一个回溯题目，感觉很猛，自己完全想不出来那种。。。后面还要多加努力。