总结:动态规划主要就四步(原始数据为int[][] arr)
1. 定义存储中间状态的数组；(可以根据条件给出或问题找出需要定义的数组中间变量)例如：dp[i][j]
2. 找到后一个状态与前一个状态的关系，(也可以是从后向前推就是前一个和后一个的关系)
例如：dp[i][j]=dp[i-1][j-1]+arr[i][j]/dp[i][j-1]等关系可以通过自己演草纸上推到一下
3. 找到dp[][]数组的初始几个值
4. 按照关系，将arr数组从前向后/从后向前推直到终止；
第十题
//动态规划
public static int countVowelStrings(int n) {
if(n==0)return 0;
//定义一个二维数组存储数据
int[][] nums=new int[n][5];
for (int i = 0; i <n ; i++) {
nums[i][0]=1;
}
nums[0][1]=2;
nums[0][2]=3;
nums[0][3]=4;
nums[0][4]=5;
for (int i = 1; i < n; i++) {
for (int j = 1; j < 5; j++) {
nums[i][j]=nums[i][j-1]+nums[i-1][j];
}
}
System.out.println(123);
return nums[n-1][4];
}
第九题子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
public int lengthOfLIS(int[] nums) {
int len=nums.length;
int[][] ints=new int[len][2];
ints[0][0]=0;
ints[0][1]=1;
for (int i = 1; i <len ; i++) {
ints[i][1] = 1;
for (int j = i-1; j >=0 ; j--) {
if (nums[i] > nums[j]) {
int tem = ints[j][1] + 1;
ints[i][1]=Math.max(tem,ints[i][1]);
}
}
ints[i][0] = Math.max(ints[i - 1][0], ints[i - 1][1]);
}
System.out.println(123456);
return Math.max(ints[len-1][1],ints[len-1][0]);
}
第七题：三步上台阶
/**
* 计算台阶三步问题。有个小孩正在上楼梯，楼梯有n阶台阶，小孩一次可以上1阶、2阶或3阶。
* 实现一种方法，计算小孩有多少种上楼梯的方式。结果可能很大，你需要对结果模1000000007。
*/
public static int waysToStep(int n) {
if(n==0)return 0;
if(n==1)return 1;
if(n==2)return 2;
long[] step=new long[n+1];
//首先确定前几个固定元素0，1，2，3自己可以在纸上写一下上台阶方式
//可以得到如下
step[0]=0;
step[1]=1;
step[2]=2;
step[3]=1+step[2]+step[1];
if(n==3)return (int)step[n];
//继续向下推导我们会发现一个有趣的推论:
// step[i]=第一次走一步+step[i-1]+第一次走两步+step[i-2]+第一次走三步+step[i-3]
//step[4]=step[3]+step[2]+step[1];
//step[5]=step[4]+step[3]+step[2];
for (int i = 4; i <= n; i++) {
long tem=(step[i-1]+step[i-2]+step[i-3]);
//根据题意取模运算就是取余数
step[i]=tem>1000000007?tem%1000000007:tem;
}
return (int)step[n];
}
例三题：不同的子序列
注：这是一道困难题（ps我也是看题解分析学会了正向解析）
public static int numDistinct(String s, String t) {
int lenj=s.length();
int leni=t.length();
//定义一个二维数组表示第i行第j列s与t的前几项匹配个数
int[][] dp=new int[leni+1][lenj+1];
//初始化第一行均为1如图中分析
for (int i = 0; i < lenj+1; i++) {
dp[0][i]=1;
}
for (int i = 1; i <= leni; i++) {
//获取当前t的i坐标对应的char
char tTem=t.charAt(i-1);
for (int j = 1; j <= lenj; j++) {
//如果当前行上s的j下标的char与t下的i下标对应的char相等则满足
//dp[i][j]=dp[i-1][j-1]+dp[i][j-1];否则当前行对应数量与上一行无关
//即等于此行前一个匹配的数量dp[i][j]=dp[i][j-1]
if(tTem==s.charAt(j-1)){
dp[i][j]=dp[i-1][j-1]+dp[i][j-1];
}else{
dp[i][j]=dp[i][j-1];
}
}
}
return dp[leni][lenj];
}
例二题：按摩师
/**
* dp按摩师最大的工作时间
*/
public static int massage(int[] nums) {
//定义最终的结果以及当数组长度为0，1，2，时的情况
int len=nums.length;
if(len==0)return 0;
if(len==1)return nums[0];
if(len==2)return Math.max(nums[0],nums[1]);
//由于不能连续工作，因此之可能是第i个前最大和为：n[i]=n[i-2]/n[i-3]+nums[i]
//定义前i项之和arr:因此根据推倒方程式可知arr0,arr1,arr2
int[] arr=new int[len];
arr[0]=nums[0];
arr[1]=nums[1];
arr[2]=nums[2]+nums[0];
for (int i = 3; i <len ; i++) {
arr[i]=Math.max(arr[i-2],arr[i-3])+nums[i];
}
//因此最终答案一定会在len-1或len-2的位置上
return Math.max(arr[len-1],arr[len-2]);
}
注:例一题：找到连续最大子字符串
首先是推导草纸：略有凌乱哈
/**
* 动态规划基础题
*/
public static int maxSubArray1(int[] nums) {
if(nums.length==1){
return nums[0];
}
int endMax=nums[0];
//定义从前向后的连续数之和的集合
int[] temNum=new int[nums.length];
temNum[0]=nums[0];
for (int i = 1; i <nums.length ; i++) {
//找到最大的前i项之和（因为是连续子字符串所以通过推到
// 很容易发现temNum[i]=temNum[i-1]+nums[i]或nums[i]取最大的定义第i位的最大和值
temNum[i]=Math.max(temNum[i-1]+nums[i],nums[i]);
//找出当前最大的在最大和数组中
endMax=Math.max(temNum[i],endMax);
}
return endMax;
}
例四题奇数必输偶数必赢其实。。自己写推论可以发现
/**
* 赢得最终：小明小芳在数字N下依次取i，使得N%i==0;i可以为1，都尽力去赢
* 小芳先选择：
* @param N
* @return
*/
public static boolean divisorGame(int N) {
//根据题意很容易知道定义一个选择结果推导数组boolean[] b
boolean[] booleans=new boolean[N+1];
//当n为1时和n为2时很容易分析出初始值
booleans[1]=false;
booleans[2]=true;
//从第三位开始继续遍历
for (int i = 3; i <= N; i++) {
//即不让堆放赢，为当!booleans[i-j]&&i%j==0时有booleans[i]=true;
//并且我们可以知道j<i/2;,大于计算无意义
for (int j = 1; j < i/2; j++) {
if((!booleans[i-j])&&(i%j==0)){
booleans[i]=true;
break;
}
}
}
return booleans[N];
}
第六题：买卖股票最佳利润一次交易
/**
* dp动态规划提
* 写了三种方式
* 第一种二维数组费空间
* 第二种一维数组
* 第三种定义一个变量
*/
public static int maxProfit(int[] prices) {
int len=prices.length;
if(len<2)return 0;
if(len==2)return Math.max(prices[1] - prices[0], 0);
/*int[][] ints=new int[len][len];
for (int i = 0; i <len ; i++) {
ints[i][i]=0;
}
for (int i = 0; i < len; i++) {
for (int j = i+1; j < len; j++) {
ints[i][j]=Math.max(prices[j]-prices[i],ints[i][j-1]);
if(i>0){
ints[i][j]=Math.max(ints[i][j],ints[i-1][j]);
}
}
}
return ints[len-2][len-1];*/
/*int[] dp=new int[len];
dp[0]=0;dp[1]=Math.max(prices[1] - prices[0], 0);
for (int i = 2; i < len; i++) {
for (int j = 0; j <i ; j++) {
dp[i]=Math.max(dp[i],prices[i]-prices[j]);
}
dp[i]=Math.max(dp[i],dp[i-1]);
}
return dp[len-1];*/
int minNum=Integer.MAX_VALUE;
int maxNum=0;
for (int i = 0; i < len; i++) {
if(prices[i]<minNum){
minNum=prices[i];
}else if(prices[i]-minNum>maxNum){
maxNum=prices[i]-minNum;
}
}
return maxNum;
}
第七题：数组的每个下标作为一个阶梯，第 i 个阶梯对应着一个非负数的体力花费值 cost[i]（下标从 0 开始）。
public static int minCostClimbingStairs(int[] cost) {
int len=cost.length;
if(len<=1)return 0;
if(len==2)return Math.min(cost[0],cost[1]);
//定义有一个二维数组只有两个元素的第一个表示不选当前元素，第二个表示选择当前元素
int[][] num=new int[len][2];
num[0][0]=0;num[0][1]=cost[0];
num[1][0]=num[0][1];num[1][1]=cost[1];
for (int i = 2; i < len; i++) {
//如果当前元素未选择咋前一个元素一定选择了
num[i][0]=num[i-1][1];
//当前元素选择则前一个元素找出最大的和
num[i][1]=Math.min(num[i-1][0],num[i-1][1])+cost[i];
}
//System.out.println("123");
return Math.min(num[len-1][0],num[len-1][1]);
}
第八题最大子序列大小
/**
* 给定一个整数数组，找出总和最大的连续数列，并返回总和。
*/
public static int maxSubArray123(int[] nums) {
int len=nums.length;
if(len==1)return nums[0];
//定义一个返回前i个的数组的最大和---一推到直接可以观察到，，
//所以最大数一定出自其中即为从前向后找都在一个循环里方便查询
int max=nums[0];
int[] data=new int[len];
data[0]=nums[0];
for (int i = 2; i < len; i++) {
data[i]=Math.max(data[i-1]+nums[i],nums[i]);
max=Math.max(data[i],max);
}
return max;
}
最后一到基础好简单哈哈
/**
* dp第八题
*/
public static int climbStairs(int n) {
if(n==0)return 0;
//定一个数组表示上台阶所走的总路程
//根据题意很容易找出地推公式。。。
int[] nus=new int[n];
nus[0]=1;
if(n==1)return nus[n-1];
nus[1]=2;
for (int i = 2; i < n; i++) {
nus[i]=nus[i-1]+nus[i-2];
}
return nus[n-1];
}
第十一题：最大相同子字符串长度中等难度
public int longestCommonSubsequence(String text1, String text2) {
String t1;String t2;
if(text1.length()>text2.length()){
t1=text1;
t2=text2;
}else{
t1=text2;
t2=text1;
}
char[] chars2=t2.toCharArray();
char[] chars1=t1.toCharArray();
if(chars2.length==0)return 0;
int[][] num=new int[chars2.length][chars1.length];
num[0][0]=chars2[0]==chars1[0]?1:0;
for (int i = 0; i < chars2.length; i++) {
for (int j = 0; j < chars1.length; j++) {
if(i==0){
num[0][j]=chars2[0]==chars1[j]?1:j>0?num[0][j-1]:0;
}else if(j==0){
num[i][0]=chars2[i]==chars1[0]?1:num[i-1][0];
}else {
num[i][j] = Math.max( num[i - 1][j] , num[i][j - 1]);
if (chars1[j] == chars2[i]) num[i][j]=Math.max(num[i][j],num[i-1][j-1]+1);
}
}
}
System.out.println(123);
return num[chars2.length-1][chars1.length-1];
}
作者：jing-tian-ming-2
链接：https://leetcode-cn.com/problems/longest-common-subsequence/solution/ao-li-gei-dong-tai-gui-hua-by-jing-tian-wbxw2/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
地十二题
public int countNumbersWithUniqueDigits(int n) {
if(n==0)return 1;
if(n>10)return 0;
int[] num=new int[11];
int tem=9*9;
num[1]=10;
num[2]=num[1]+tem;
for (int i = 2; i < 10; i++) {
tem=tem*(10-i);
num[i+1]=num[i]+tem;
}
return num[n];
}
作者：jing-tian-ming-2
链接：https://leetcode-cn.com/problems/count-numbers-with-unique-digits/solution/dpdong-tai-hua-gui-hua-by-jing-tian-ming-jw3o/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
注意：这里是我的leetcode大家一起加油哈！https://leetcode-cn.com/problems/longest-common-subsequence/solution/ao-li-gei-dong-tai-gui-hua-by-jing-tian-wbxw2/