网站开发原则百度的合作网站有哪些
动态规划：通俗一点说就是大事化小，小事化无的思想。其在处理问题时候，会将小问题的结果保存起来，供大问题求解的时候使用。
1、 动态规划的三个特点
- 把原来的问题分解成几个相似的子问题
- 所有的子问题只需要解决一次
- 求解的过程中，需要保存子问题的解
2、动态规划的本质：是对问题状态的定义和状态转移方程的定义（一个状态---->l另外一个状态的）
3、动态规划问题从以下四个角度考虑
- 状态定义
- 状态转移方程的定义
- 状态的初始化(值是确定的）
- 返回结果
应用场景：最大值、最小值、判断方法是否可行，方案个数等
经典面试题1
题目描述： 大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0）。
n<=39
- 状态定义：F(n),第n项的值
- 状态转移方程的定义：F(n)=F(n-1)+F(n-2)
- 状态的初始化:F(1)=F(2)=1
- 返回结果:F(n)
public class Solution {public int Fibonacci(int n) {if(n==0){return 0;}if(n==1||n==2){return 1;}//F(1)int a=1;//F(2)int b=1;int sum=0;for(int i=3;i<=n;i++){//F(n)=F(n-1)+F(n-2)sum=a+b;a=b;b=sum;}return sum;}
}经典面试题2
题目描述： 一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多
少种跳法。
- 状态定义：F(n),跳法第n次跳上台阶的
- 状态转移方程的定义：
最后一步跳一级：则有F(n-1)方法
最后一步跳两级：则有F(n-2)方法
…
最后一步跳n-1级：则有F(1)方法
因此：
F(n)=F(n-1)+F(n-2)+F(n-3)+…+F(1)
F(n-1)=F(n-2)+F(n-3)+…+F(1)
F(n)=2*F(n-1) - 状态的初始化:F(1)=1
- 返回结果:F(n)
public class Solution {public int JumpFloorII(int target) {if(target<=0){return 0;}//初始状态if(target=1){return 1;}int sum=1;/*for(int i=2;i<=n;i++){//F(n)=2*F(n-1）sum*=2;}*///降低时间复杂度sum=1<<(n-1);return sum;return sum;}
}
经典面试题3
题目描述： 一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。
n<=39
- 状态定义：F(n),第n项的值
- 状态转移方程的定义：F(n)=F(n-1)+F(n-2)
- 状态的初始化:F(0)=0 F(1)=1
- 返回结果:F(n)
public class Solution {public int JumpFloor(int target) {if(target<=0){return 0;}if(target<=3){return target;}int temp1=2;int temp2=3;int sum=0;for(int i=4;i<=target;i++){sum=temp1+temp2;temp1=temp2;temp2=sum;}return sum;}
}
经典面试题4
**题目描述：**我们可以用21的小矩形横着或者竖着去覆盖更大的矩形。请问用n个21的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法？。
n<=39
跟青蛙只能跳一次和两次台阶一样
- 状态定义：F(n),第n项的方法,
- 状态转移方程的定义：F(n)=F(n-1)+F(n-2)
- 状态的初始化:F(0)=0 F(1)=1
- 返回结果:F(n)
public class Solution {public int RectCover(int target) {if(target<=0){return 0;}if(target<=2){return target;} int a=1;int b=2;int sum=0;for(int i=3;i<=target;i++){sum=a+b;a=b;b=sum;}return sum;}}
经典面试题5
题目描述： HZ偶尔会拿些专业问题来忽悠那些非计算机专业的同学。今天测试组开完会后,他又发话了:在古老的一维模式识别中,常常需要计算连续子向量的最大和,当向量全为正数的时候,问题很好解决。但是,如果向量中包含负数,是否应该包含某个负数,并期望旁边的正数会弥补它呢？例如:{6,-3,-2,7,-15,1,2,2},连续子向量的最大和为8(从第0个开始,到第3个为止)。给一个数组，返回它的最大连续子序列的和，你会不会被他忽悠住？(子向量的长度至少是1)
- 状态定义：F(i),截止到i，最大子数列F[i],
- 状态转移方程的定义：
F(i): max(F(i-1)+a[i],a[i])
F(1):6
F(2): -3 , -3+6, max(F(1)+a[i],a[i]
F(3):-2,-2±3,-2±3+6,max(F(2)+a[i],a[i] - 状态的初始化:F(0)=a[0]
- 返回结果:返回最大的子数列 max(F[i])
public class Solution {public int FindGreatestSumOfSubArray(int[] array) {int[] ret=new int[array.length];//找截止到i的最大子序列ret[0]=array[0];for(int i=1;i<array.length;i++){ret[i]=Math.max(ret[i-1]+array[i],array[i]);}//在所有子序列里面找到最大的int maxNum=ret[0];for(int i=1;i<ret.length;i++){maxNum=Math.max(maxNum,ret[i]);}return maxNum;}
}
经典面试题7
题目描述： 给定字符串s和单词字典dict，确定s是否可以被分割成一个或多个字典单词的空格分隔序列。
例如，给定
s =“leetcode”，
dict = [“leet”，“code”]。
返回true，因为“leetcode”可以被分段为“leet code”。
- 状态定义：F(i),前i个字符能否被分割,
- 状态转移方程的定义：(j<i)&&(F(j)&&(j+1~i)能否被分割
- 状态的初始化:F(0)=true
- 返回结果:F(n)
public class Solution {public boolean wordBreak(String s, Set<String> dict) {if(s.isEmpty()){return false;}if(dict.isEmpty()){return false;}Iterator<String> iterator=dict.iterator();//得到字典单词的最大长度int maxLength=0;while (iterator.hasNext()){int length=iterator.next().length();if(length>maxLength){maxLength=length;}}//用来储存，前j是否可以分割,注意边界为s.length()+1boolean [] booleans=new boolean[s.length()+1];//" "booleans[0]=true;for(int i=1;i<=s.length();i++){for (int j=i-1;j>=0;j--){//如果子串大于字典最大的单词长度，跳过if((i-j)>maxLength){break;}//(F(j)&&(j+1~i)能否被分割if(booleans[j]&&dict.contains(s.substring(j,i))){booleans[i]=true;break;}}}return booleans[s.length()];}
}
经典面试题8
题目描述：
给定一个三角形，找到从上到下的最小路径总和。您可以移动到下面一行中相邻数字的每一步。
例如，给定以下三角形
[
[ 2 ]，
[ 3,4 ]，
[6，5，7]，
[4，1，8,3]
]
从上到下的最小路径总和为11（即，2 + 3 + 5 + 1 = 11）。
注意：
如果只能使用O（n）额外空间来执行此操作，则可以使用 额外点，其中n是三角形中的总行数
方法1：
- 状态定义：子状态：从(0,0)到(1,0),(1,1),(2,0),…(n,n)的最短路径和
F(i,j): 从(0,0)到(i,j)的最短路径和 - F(i,j) = min( F(i-1, j-1), F(i-1, j)) + triangle[i][j]
- 状态的初始化:F(0,0) = triangle[0][0]
- 返回结果:min(F(n-1, i))
import java.util.ArrayList;
public class Solution {public int minimumTotal(ArrayList<ArrayList<Integer>> triangle) {if(triangle.isEmpty()){return 0;}int[][] dp=new int[triangle.size()+1][triangle.size()+1];//初始状态dp[0][0]=triangle.get(0).get(0);for(int i=1;i<triangle.size();i++){for(int j=0;j<=i;j++){//处理边界if(j==0){dp[i][j]=dp[i-1][j];}else if (j==i){dp[i][j]=dp[i-1][j-1];}else {dp[i][j]=Math.min(dp[i-1][j],dp[i-1][j-1]);}//F(i,j) = min( F(i-1, j-1), F(i-1, j)) + triangle[i][j]dp[i][j]=dp[i][j]+triangle.get(i).get(j);}}//到达最后一行元素，查看谁的数值最小int result=dp[triangle.size()-1][0];for(int i=1;i<triangle.size();i++){result=Math.min(dp[triangle.size()-1][i],result);}return result;}
}
方法2：
- 状态定义：
子状态：从(n,n),(n,n-1),…(1,0),(1,1),(0,0)到最后一行的最短路径和
F(i,j): 从(i,j)到最后一行的最短路径和 - 状态转移方程的定义：min( F(i+1, j), F(i+1, j+1)) + triangle[i][j]
- 状态的初始化:F(n-1,0) = triangle[n-1][0], F(n-1,1) = triangle[n-1][1],…, F(n-1,n-1) = triangle[n-1][n-1]
- 返回结果:F(0, 0)
import java.util.ArrayList;
public class Solution {public int minimumTotal(ArrayList<ArrayList<Integer>> triangle) {int length=triangle.size();int[][] dp=new int[length+1][length+1];//获取最后一行元素for(int j=0;j<length;j++){dp[length-1][j]=triangle.get(length-1).get(j);}//从倒数第二行开始for(int i=length-2;i>=0;i--){for(int j=0;j<=i;j++){//F(i,j) = min( F(i+1, j), F(i+1, j+1)) + triangle[i][j]dp[i][j]=Math.min(dp[i+1][j],dp[i+1][j+1])+triangle.get(i).get(j);}}return dp[0][0];}
}
经典面试题9
题目描述：
在一个m*n的网格的左上角有一个机器人，机器人在任何时候只能向下或者向右移动，
机器人试图到达网格的右下角，有多少可能的路径。
1）状态的定义：
从左上角到（i，j)路径总数
2）状态的转移方程:
F(i,j)=F(i-1,j)+F（i，j-1）
3）状态的初始化（值确定的）
Ｆ（０，０）＝１ ＝Ｆ（ｉ，０）＝Ｆ（０，ｊ）
第一行，第一列也是１
4）返回的结果
return PathNum[n-1][m-1]
public class Solution {public int uniquePaths(int m, int n) {if(n<0||m<0){return 0;}int [][] array=new int[m][n];//初始化，第一行，第一列都为1for(int i=0;i<m;i++){array[i][0]=1;}for(int j=0;j<n;j++){array[0][j]=1;}for(int i=1;i<m;i++){for(int j=1;j<n;j++){array[i][j]=array[i-1][j]+array[i][j-1];}}return array[m-1][n-1];}
}