初识动态规划，java 程序设计教程第三版机械工业出版社
}
if(n==1||n==2){
return 1;
}
int f1=1;
int f2=1;
int f3=0;
for(int i=3;i<=n;i++){
f3=f1+f2;
f1=f2;
f2=f3;
}
return f3;
}
很多动规问题都可以转化成 Fib 数列解决
[](
)二、青蛙跳台阶
==========================================================================
先是变态青蛙跳台阶，有 n 阶台阶，青蛙可以每次跳一个，二个…或者 n 个
分解问题：
1.状态定义 F(n)
2.状态间转移方程定义 F(n)=2F(n-1)
3.状态的初始化 F(1)=1
4.返回结果 F(n)
public static int climbingStairs(int n){
int res=1;
for(int i=2;i<=n;i++){
//F（n）=2F（n-1）
res*=2;
}
return res;
}
之后是正常的青蛙，每次只能跳一个台阶或者两个台阶（斐波那契数列）
[leetcode 70 题](
)
1.状态定义 F（n）
2.状态间转移方程定义 F（n）=F(n-1)+F(n-2)
3.状态初始化 F（1）=1；
4.返回结果 F（n）
public static int climbingStairs1(int n){
if(n==1||n==2){
return n;
}
int f1=1;
int f2=2;
int f3=0;
for(int i=3;i<=n;i++){
f3=f1+f2;
f1=f2;
f2=f3;
}
return f3;
}
[](
)三、矩阵覆盖
=========================================================================
[题目链接](
)
分析问题后依旧是斐波那契数列
1.状态定义 F(n)
2.状态间转移方程定义 F(n)=F(n-1)+F(n-2)
3.状态的初始化 F(1)=1 F(2)=2
4.返回结果 F(n)
public static int rectCover(int target) {
if(target==1||target==2){
return target;
}
int t1=1;
int t2=2;
int t3=0;
for(int i=3;i<=target;i++){
t3=t1+t2;
t1=t2;
t2=t3;
}
return t3;
}
}
或者使用数组记录
public static int rectCover1(int target){
if(target==0){
return 0;
}
int []dp=new int[target+1];
dp[0]=1;
dp[1]=2;
for(int i=2;i<target;i++){
dp[i]=dp[i-1]+dp[i-2];
}
return dp[target-1];
}
[](
)四、最大连续字数组和
=============================================================================
[leetcode 53 题](
)
这种题使用动态规划来做的话就和前面几个不相同了，因为其无法定义状态间转移方程
所以就把大问题化成先问题去解决
例如求最大连续字数组和，先求前 i 个最大字数组的和，最终求最大连续字数组和
时间复杂度 O（n）,空间复杂度 O（1）做法
public int maxSubArray(int[] nums) {
int res=nums[0];
for(int i=1;i<nums.length;i++){
//比较当前值和当前值加上前一个值的大小
nums[i]=Math.max(nums[i-1]+nums[i],nums[i]);
res=Math.max(nums[i],res);
}
return res;
}
或者另外一种如果前 i 项最大子序和<=0 就重新赋值为下一个数值，记录 max 最大值
public static int maxSubArray(int[] nums) {
int max=nums[0];
int count=nums[0];
for(int i=1;i<nums.length;i++){
if(count<=0){
count=nums[i];
}else {
count+=nums[i];
}
max=Math.max(max,count);
}
return max;
}
[](
)五、字符串分割
==========================================================================
[题目链接](
)
先把大问题化成小问题 前 i 个字母能否成功分割
状态转移方程是 j<i&&F(j)&&[j,i-1] 即 F(j)为 true [j,i-1]也为 true 这样可以存储 true
例如：给定 s=“nowcode” 已知 now 和 code 在词典中，在找到 cow 后就可以从 j+1 位置找到 i 位置单词是否能在词典中找到
举例说明：
例如 dict 中 [le ,et ,co ,de]是单词
那么当 leetcode 字符串传来时
F(1) false ——— F(2) true ——— F(3)false ————F(4)true
F(5) false——— F(6) true ——— F(7)false ——— F(8) true
即判断时可以借助前面的结果来判断 例如 F（4）利用 F（2）为 true 只需要判断后两个字母是否能组成单词即可。
public boolean wordBreak(String s, Set<String> dict) {
if(s.length()==0){
return true;
}
boolean[]array=new boolean[s.length()+1];
for(int i=1;i<=s.length();i++){
//1~i 整体范围是一个单词
if(dict.contains(s.substring(0,i))){//substring 是从 0 到 i-1 位置
array[i]=true;
continue;
}
for(int j=i-1;j>0;j--){
//部分判断 一部分为前面验证过的 true 判断后面的也为 true
if(array[j]&&dict.contains(s.substring(j,i))){//substring 是从 j 位置到 i-1 位置
array[i]=true;
break;
}
}
}
return array[s.length()];
}
[leetcode 139 题](
)
也是这样的字符串拆分 双 80%
public boolean wordBreak(String s, List<String> wordDict) {
boolean []array=new boolean[s.length()+1];
for(int i=1;i<=s.length();i++){
if(wordDict.contains(s.substring(0,i))){
array[i]=true;
continue;
}
for(int j=i-1;j>0;j--){
if(array[j]&&wordDict.contains(s.substring(j,i))){
array[i]=true;
break;
}
}
}
return array[s.length()];
}
[](
)六、三角矩阵求最短路径
==============================================================================
[牛客题目链接](
)
[leetcode 120 题](
)
给定一个三角矩阵，找出自顶向下的最短路径和，每一步可以移动到下一行相邻的数字
首先确定相邻元素的概念：
1.如果在 F（i，j）下一行相邻元素就是 （i+1，j）(i+1，j+1)
如果从下往上推的话，从 F（i，j）位置往上的相邻位置就是（i-1,j）(i-1,j-1)
2.状态转移方程是 F(min)=Math.min(F(i-1,j),(i-1,j-1))+a(i，j)// 从相邻位置中找到最小值，之后加上当前位置坐标
注意每一行的第一列和最后一列只有一条路径
第一列 F（i,0)=F(i-1,0)+a[i][0]
最后一列 F（i，i）=F(i-1,i-1)+a[i][i]
3.初始状态
F（0，0）=a[0][0]
最终思想是从上往下求（先判断边界情况，第一列只有一条路径，最后一列也只有一条路径都加上当前坐标值就好，）之后找最小路径值就可以了。
public int minimumTotal(List<List<Integer>> triangle) {
List<List<Integer>> list=new ArrayList<>();
for(int i=0;i<triangle.size();i++){
list.add(new ArrayList<>());
}
//先定义初始值 在 0 位置加上（0，0）坐标的值
list.get(0).add(triangle.get(0).get(0));
//之后遍历判断特殊情况 每一行的第一个 ，每一行的最后一个
for(int i=1;i<triangle.size();i++){
int count=0;//当前路径和
for(int j=0;j<=i;j++){
if(j==0){
count=list.get(i-1).get(j);
}else if(i==j){
count=list.get(i-1).get(j-1);
}else {
count=Math.min(list.get(i-1).get(j),list.get(i-1).get(j-1));
}
list.get(i).add(triangle.get(i).get(j)+count);
}
}
//之后找到 list 中到目标路径的最小值即可
int len=triangle.size();
int min=list.get(len-1).get(0);
for(int i=1;i<len;i++){
min=Math.min(min,list.get(len-1).get(i));
}
return min;
}
[](
)七、不同路径
=========================================================================
[leetcode 62 题](
)
找到状态转移方程 F[i] [j]=F[i-1] [j]+F[i] [j-1];
定义初始状态 即边界值 F[0] [i]=1 F[j] [0]=1 即可
还未添加个人签名 2021.03.18 加入
还未添加个人简介
评论