目录
第1题 Fibonacci
第2题 字符串分割(Word Break)
.第3题 三角矩阵(Triangle)
第4题 路径总数(Unique Paths)
第5题 最小路径和(Minimum Path Sum)
第6题 背包问题
第7题 回文串分割(Palindrome Partitioning)
第8题 编辑距离(Edit Distance)
第9题 不同子序列(Distinct Subsequences)
第1题 Fibonacci
分析问题:
1. 状态定义F(i):第i个项的值
2. 状态间的转移方程定义:F(i)=F(i-1)+F(i-2)
3. 状态的初始化:F(0)=0 F(1)=1
4. 返回结果:F(i)
public class Solution {
public int Fibonacci(int n) {
//创建数组,保存状态的值
int[] dp=new int[n+1];
dp[0]=0;
dp[1]=1;
//F(i)=F(i-1)+F(i-2)
//从第二个开始到第n个结束
for(int i=2;i<=n;i++){
dp[i]=dp[i-1]+dp[i-2];
}
return dp[n];
}
}
第2题 字符串分割(Word Break)
F(i) F(j) && [j+1,i] 可以在词典中找到
分析问题:
1. 状态定义F(i):
字符串s是否可以分割
2. 状态间的转移方程定义:
F(i):(j<i) && F(j) $$ [j+1,i] 是否可以在词典中找到
3. 状态的初始化:
F(0)=true
4. 返回结果:
F(字符串长度):f(s.size())
public class Solution {
public boolean wordBreak(String s, Set<String> dict) {
boolean[] dp=new boolean[s.length()+1];
dp[0]=true;
for(int i=1;i<=s.length();i++){
for(int j=0;j<i;j++){
if(dp[j] && dict.contains(s.substring(j,i))){
dp[i]=true;
break;
}
}
}
return dp[s.length()];
}
}
.第3题 三角矩阵(Triangle)
问题:从顶部到底部的最小路径和
状态:从(0,0)到(i,j)的最小路径和
状态转移方程:
(0
F(i,j): min(F(i-1,j-1),F(i-1,j))+array[i][j] 前一个最小的和当前的值的和
(j==0 || j==i):F(i,j):
j==0 ; (F(i-1,0)+array[i][0]
j==i;F(i-1,j-1)+array[i][j]
初始状态:
F(0,0)=array[0][0]
返回结果:
min(F(row-1,j))
public int minimumTotal(ArrayList<ArrayList<Integer>> triangle) {
if(triangle.isEmpty()){
return 0;
}
List<List<Integer>> minPathSum=new ArrayList<>();
for(int i=0;i<triangle.size();i++){
minPathSum.add(new ArrayList<>());
}
//F(0)(0)初始化
minPathSum.get(0).add(triangle.get(0).get(0));
for(int i=1;i<triangle.size();i++){
int curSum=0;
for(int j=0;j<=i;j++){
if(j==0){
curSum=minPathSum.get(i-1).get(0);
}
else if(j==i){
curSum=minPathSum.get(i-1).get(j-1);
}else{
curSum=Math.min(minPathSum.get(i-1).get(j),minPathSum.get(i-1).get(j-1));
}
//之前的值加当前的值
minPathSum.get(i).add(triangle.get(i).get(j)+curSum);
}
}
int size=triangle.size();
//值为最后一行第一个
int allMin=minPathSum.get(size-1).get(0);
for (int i = 1; i < size; i++) {
//遍历最后一行找到最小值
allMin=Math.min(allMin,minPathSum.get(size-1).get(i));
}
return allMin;
}
第4题 路径总数(Unique Paths)
状态:从(0,0)到任意一点的个数
转移方程:F(i,i)=F(i-1,j)+F(i,j-1); 上面和左面的个数和
初识状态:F(i,0)=F(0,j)=1;
返回结果: F(m-1,n-1)
public int uniquePaths (int m, int n) {
int[][] arr=new int[m][n];
//初始化
for(int i=0;i<m;i++){
arr[i][0]=1;
}
for(int i=0;i<n;i++){
arr[0][i]=1;
}
//过程
for(int i=1;i<m;i++){
for(int j=1;j<n;j++){
arr[i][j]=arr[i-1][j]+arr[i][j-1];
}
}
return arr[m-1][n-1];
}
第5题 最小路径和(Minimum Path Sum)
状态: 从(0,0)到(i,j)的最短路径和
状态转移方程:F(i,j)=min{F(i-1,j),,F(i,j-1)}+array[i][j]
i==0 F=F(0,j-1)+array[0][j]
j==0 F(i-1,0)+array[i][j]
初始化 F(0,0)=array[0][0]
返回结果:F(m-1,n-1)
public int minPathSum (int[][] grid) {
int n=grid.length;
int m=grid[0].length;
if(n==0 || m==0){
return 0;
}
//在grid的基础上改
for(int i=1;i<n;i++){
grid[i][0]=grid[i-1][0]+grid[i][0];
}
for(int i=1;i<m;i++){
grid[0][i]=grid[0][i-1]+grid[0][i];
}
for(int i=1;i<n;i++){
for(int j=1;j<m;j++){
grid[i][j]=Math.min(grid[i-1][j],grid[i][j-1])+grid[i][j];
}
}
return grid[n-1][m-1];
}
第6题 背包问题
文章来源地址https://www.toymoban.com/news/detail-462673.html
状态:F(i,j):从前I个商品中选择,包的大小为j时,最大值
状态转移方程:
1.能放入:
1.不放:和前一个相同
2.放入:大小剪去改商品的大小,价值增加
2.不能放入:
和前一个相同
初识状态:
第0行和第0列都为0,表示 没有商品或者包大小为0
F(0,j)=F(i,0)=0;
返回结果F(m,n)
public int backPackII(int m, int[] a, int[] v) {
//得到商品总个数
//包大小为0,或没有商品直接返回
//创建二维数组:表示背包总价值 列表示放入的商品个数 行表示包的大小
//初始化 行为0,或列为0,结果都为0
//过程 判断商品大小,有放入和不放入两种
//返回
int num=a.length;
if(m==0 || num==0){
return 0;
}
// 0,0返回,所以要+1
int[][] dp=new int[num+1][m+1];
for(int i=0;i<=num;i++){
dp[i][0]=0;
}
for(int i=0;i<=m;i++){
dp[0][i]=0;
}
//从1到num开始遍历
for(int i=1;i<=num;i++){
for(int j=1;j<=m;j++){
//a,v数组是从0开始的
//dp从1开始
if(a[i-1]>j){
dp[i][j]=dp[i-1][j];
}else{
int cur=dp[i-1][j-a[i-1]]+v[i-1];
dp[i][j]=Math.max(cur,dp[i-1][j]);
}
}
}
return dp[num][m];
第7题 回文串分割(Palindrome Partitioning)
如果从j+1到i为回文串,也知道j之前的分割次数,就在切一次,保证都是回文串
F(i):[i,i]是回文串:0
j<i && [j+1][i]是回文串:min(f(i)+1)
状态:f(i):s的前i个字符最小的分割次数
状态转移方程:
如果j到i-1是是回文串,f(j)+1
F(i,j):
初始状态:
f(i)=i-1 从1开始 最大分割次数为每一个字母都分割一次
循环判断首尾元素是否相同,如果全部相同,则是回文串
import java.util.*;
public class Solution {
/**
*
* @param s string字符串
* @return int整型
*/
public int minCut (String s) {
int len=s.length();
if(len==0){
return 0;
}
int[] minCut=new int[len+1];
//初始化
for(int i=0;i<=len;i++){
minCut[i]=i-1;
}
for (int i = 1; i <=len ; i++) {
for (int j = 0; j <=i ; j++) {
//前面的循环就直接可以拿到0-j是不是回文串的结果
//前面的结果是已知的,要判断后面的是不是回文串
if(isPal(s,j,i-1)){
minCut[i]=Math.min(minCut[i],minCut[j]+1);
}
}
}
return minCut[len];
}
private boolean isPal(String s, int start, int end) {
while(start<end){
if(s.charAt(start)!=s.charAt(end)){
return false;
}
start++;
end--;
}
return true;
}
}
第8题 编辑距离(Edit Distance)
问题:word1到word2的编辑距离
子问题:word1局部到word2局部的编辑距离
状态:
F(i,j):word1前i个字符到word2前j个字符的编辑距离
min(删除,插入,替换(相等不加一))
F(i,j) = min { F(i-1,j)+1, F(i,j-1) +1, F(i-1,j-1) +(w1[i]==w2[j]?0:1) }
i删除 增加i 如果i,j对应的字符相等,不操作,如果不相等,+1
初始化:F(i,0)=i
F(0,i)=i
返回结果:F(m,n)
步骤:
- 有一个为空,返回另一个的长度
- 初始化
- 状态变化:从1开始
- 得到插入和删除的最小值
- 判断i,j对应的元素是否相等
- 替换和1得到的值取最小值
- 返回
import java.util.*;
public class Solution {
/**
*
* @param word1 string字符串
* @param word2 string字符串
* @return int整型
*/
public int minDistance (String word1, String word2) {
// write code here
if(word1.isEmpty() || word2.isEmpty()){
return Math.max(word1.length(),word2.length());
}
int row=word1.length();
int col=word2.length();
int[][] dp=new int[row+1][col+1];
for(int i=0;i<=row;i++){
dp[i][0]=i;
}
for(int i=0;i<=col;i++){
dp[0][i]=i;
}
for(int i=1;i<=row;i++){
for(int j=1;j<=col;j++){
int cur=Math.min(dp[i-1][j],dp[i][j-1])+1;
if(word1.charAt(i-1) ==word2.charAt(j-1)){
dp[i][j]=Math.min(dp[i-1][j-1],cur);
}else{
dp[i][j]=Math.min(dp[i-1][j-1]+1,cur);
}
}
}
return dp[row][col];
}
}
第9题 不同子序列(Distinct Subsequences)
文章来源:https://www.toymoban.com/news/detail-462673.html
- 问题:
- S中和T相同的子序列的个数
- 子问题:
- S的子串中和T相同的子序列的个数
- 状态F(i):
- S的前i个字符构成的子串中和T相同的子序列的个数
- 子串长度>=T的长度
- 在F(i,j)处需要考虑S[i] = T[j] 和 S[i] != T[j]两种情况
- 状态转移方程
- 当s[i]!=T[j]: F(i,j)=F(i-1,j)
- 当s[i]==T[i]:
- 匹配: F(i,j)=F(i-1,j-1)
- 不匹配: F(i,j)=F(i-1,j) s,t下标从0开始
- 初始化:
- F(i,0)=1 s中包含空集
- F(0,j)=0 空集中不包含
import java.util.*;
public class Solution {
/**
*
* @param S string字符串
* @param T string字符串
* @return int整型
*/
public int numDistinct (String S, String T) {
int slen=S.length();
int tlen=T.length();
//初始化
int[][] dp=new int[slen+1][tlen+1];
dp[0][0]=1;
for(int i=1;i<=slen;i++){
dp[i][0]=1;
}
for(int i=1;i<=tlen;i++){
dp[0][i]=0;
}
for(int i=1;i<=slen;i++){
for(int j=1;j<=tlen;j++){
if(S.charAt(i-1)==T.charAt(j-1)){
dp[i][j]=dp[i-1][j-1]+dp[i-1][j];
}else{
dp[i][j]=dp[i-1][j];
}
}
}
return dp[slen][tlen];
}
}
到了这里,关于动态规划2:题目的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!