1、三步问题
有个小孩正在上楼梯，楼梯有n阶台阶，小孩每次可以上1阶、两阶或者三阶。
计算小孩有多少种上楼梯的方式。结果可能很大，你需要对1000000007取模
样例输入
3
样例输出
4
样例输入
5
样例输出
13
范围
1<=n<=1000000
代码实现：
import java.util.Scanner; public class dp_1 { //三步问题 public static void main(String[] args) { Scanner sc=new Scanner(System.in); int n=sc.nextInt(); int[] dp=new int[n+3]; dp[1]=1; dp[2]=2; dp[3]=4; for (int i = 4; i <= n; i++) { dp[i]=(dp[i-1]+dp[i-2]+dp[i-3])%1000000007; } System.out.println(dp[n]); } }
2、连续数列
给定一个整数数组，找出总和最大的连续数列
样例输入
[-2,1,-3,4,-1,2,1,-5,4]
样例输出
6
当连续的子数组为[4,-1,2,1]时最大
import java.util.Arrays; import java.util.Scanner; public class demo { //连续数列 public static void main(String[] args) { Scanner sc=new Scanner(System.in); String str=sc.nextLine(); str=str.substring(1,str.length()-1); String[] a=str.split(","); int[] dp=new int[a.length]; //字符串数组转int数组 int[] s=Arrays.stream(a).mapToInt(Integer::parseInt).toArray(); dp[0]=s[0]; int max=s[0]; for (int i = 1; i < a.length; i++) { dp[i]=Math.max(dp[i-1]+s[i], s[i]); max=Math.max(max, dp[i]); } System.out.println(max); } }
3、打家劫舍
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，
影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，
如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
现在给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动报警装置的情况下，
能偷窃到的最高金额。
样例输入
[1,2,3,1]
样例输出
4
样例输入
[2,7,9,3,1]
样例输出
12
import java.util.Arrays; import java.util.Scanner; public class demo { //打家劫舍 public static void main(String[] args) { Scanner sc=new Scanner(System.in); String str=sc.nextLine(); if(str.length()==0) { System.out.println(0); return; } if(str.length()==1) { System.out.println(str); return; } str=str.substring(1,str.length()-1); String[] a=str.split(","); int[] s=Arrays.stream(a).mapToInt(Integer::parseInt).toArray(); int[] dp=new int[a.length]; dp[0]=s[0]; dp[1]=Math.max(dp[0], s[1]); for (int i = 2; i < a.length; i++) { dp[i]=Math.max(dp[i-1], dp[i-2]+s[i]); } System.out.println(dp[s.length-1]); } }
4、不同路径
不同路径
一个机器人位于一个m*n网格的左上角机器人每次只能向下或者向右移动一步。
机器人视图达到网格的右下角，问总共有多少条不同的路径？
样例输入
3 2
样例输出
3
样例输入
7 3
样例输出
28
代码实现
import java.util.Scanner; public class demo { //不同路径 public static void main(String[] args) { Scanner sc=new Scanner(System.in); int m=sc.nextInt(); int n=sc.nextInt(); int[][] dp=new int[m][n]; for (int i = 0; i < n; i++)dp[0][i]=1; for (int i = 0; i < m; i++)dp[i][0]=1; for (int i = 1; i < dp.length; i++) { for (int j = 1; j < dp[i].length; j++) { dp[i][j]=dp[i-1][j]+dp[i][j-1]; } } System.out.println(dp[m-1][n-1]); } }
5、最小路径和
最小路径和
给定一个包含非负数整数的m*n网格，请找出一条从左上角到右下角的路径，
使得路径上的数字总和为最小。
说明：每次只能向下或者向右移动一步。
输入样例
3 3 1 3 1 1 5 1 4 2 1
输出样例
7
import java.util.Scanner; public class dp_5 { //最小路径和 public static void main(String[] args) { Scanner sc=new Scanner(System.in); int m=sc.nextInt(); int n=sc.nextInt(); int[][] a=new int[m][n]; for (int i = 0; i < a.length; i++) { for (int j = 0; j < a[i].length; j++) { a[i][j]=sc.nextInt(); } } int[][] dp=new int[m][n]; dp[0][0]=a[0][0]; for (int i = 1; i < m; i++)dp[0][i]=dp[0][i-1]+a[0][i]; for (int i = 1; i < n; i++)dp[i][0]=dp[i-1][0]+a[i][0]; for (int i = 1; i < dp.length; i++) { for (int j = 1; j < dp.length; j++) { dp[i][j]=Math.min(dp[i-1][j], dp[i][j-1])+a[i][j]; } } System.out.println(dp[m-1][n-1]); } }
附加题(超经典题目，建议不会的背下来公式)：
最长公共子序列
给定两个字符串text1和text2，返回这两个字符串的最长公共子序列的长度。
如果不存在公共子序列则返回0.
一个字符串的子序列是指这样一个新的字符串：它是由原字符串在不变字符串的相对顺序情况下删除某些字符后组成的新字符串。
例如“ace”是“abcde”的子序列，但是“aec”不是“abcde”的子序列
两个字符串公共子序列是这两个字符串所共同拥有的子序列。
样例输入
1. abcde 2. ace
样例输出
3
样例输入
1. abc 2. abc
样例输出
3
import java.util.Scanner; public class dp_6 { //最长公共子序列 public static void main(String[] args) { Scanner sc=new Scanner(System.in); String text1=sc.nextLine(); String text2=sc.nextLine(); int[][] dp=new int[10000][10000]; for (int i = 1; i <= text1.length(); i++) { for (int j = 1; j <= text2.length(); j++) { if(text1.charAt(i-1)==text2.charAt(j-1)) { dp[i][j]=dp[i-1][j-1]+1; }else { dp[i][j]=Math.max(dp[i-1][j], dp[i][j-1]); } } } System.out.println(dp[text1.length()][text2.length()]); } }
