林子里有两条路,我——
选择了行人稀少的那一条
它改变了我的一生。
为什么引用这首诗呢?因为就像动态规划所适应的问题一样,我们走上了不同的路,我们最终的人生
到达了不同的目的地,我们想要知道哪种最好,我们想要知道那弯曲的小路尽头我们能获得最大的成就,动态规划的神奇的地方就在于 解题过程中不用担心选择,我们只需在迈向下一步的过程中考虑有几个路口 走了这些路口我们会失去什么,会获得什么,会变成什么,动态规划会“替我们选择”。
(虽然实质也不是太“美丽”,通过暴力循环也是把路都走了遍,才知道每条路的酸甜苦辣。。)
关键:(1)dp【】或dp【】【】(状态)
(2)找怎么由之前的情况推理过来 注意推理过来的情况之间彼此的不同 小技巧:考虑最后 一步是怎么由前面过来的
(状态转移方程)
(3)可能初值需要出口 列好初值(一维一般列f【0】 二维有时列边界dp【0】【i】
dp【i】【0】 其核心还是看下面的循环要用什么初值) 然后在一层或者二层循环中
在下面的例题中仔细地体会
1.楼梯问题:一次能上1层或2层 上n层有多少种上法
(1)dp[n] n层楼梯有dp[n]种上法
(2)dp[n]=dp[n-1]+dp[n-2]//利用小技巧,我们站在最后的台阶上,由前面迈两步
或者迈一步过来,两者必然是不同的道路,故两者相加。
(3)代码

2.信封问题: 送出n封信 每封全部装错
(1)dp[n]:n封信有dp[n]种装错方法
(2)dp[n]=dp[n-1]*(n-1) 我们最后一封信装错了,有n-1个位置可以装错
其它也都装错有dp【n-1】种,在最后一封信装错到不同位置上的基础上必然是不同的装错
方法,故相乘。
(3)

3.最长递增子序列的长度:1 4 3 5 6 -》4
(1)dp[n]:以s【n】为结尾的最长递增长度//以...结尾这种巧妙设置状态方式记住,以后常用
(2)dp[n]=max{1,if(s[n]>=s[i]) dp[i]+1}//考虑最后一步,比如1,2,4,3,7,6
我们指向6了,6比3大,6也比4大,故都可以作为它们的递增序列结尾。
(3)

4.最长递增子序列的个数:1 4 3 5 6 -》2
(1) dt[n]:以s【n】为结尾的最长递增长度
dp[n]::以s【n】为结尾的最长递增长度的个数
(2)dp[n]=max{1,if(s[n]>=s[i]) dp[i]+1}
dt[n]=个数(max{1,if(s[n]>=s[i]) dp[i]+1})
5.最长公共子序列:s1和s2的序列的最长公共子序列长度

(1)dp[i][j]:s1前i个字符长度 s2前j个字符长度 的最长公共子序列长度
(2) dp[i][j]=dp[i-1][j-1]+1 s1[i]=s2[j]
dp[i][j]=max(dp[i-1][j],dp[i][j-1])
(3)

6.背包问题
有不同的钱 和不同的货物的价值 如何花最少的钱 获得最大的钱
(1) dp[i][j] 在不超过j(总钱)的情况下 前i件能达到的最大的价值
(2)dp[i][j]=max(dp[i-1][j],dp[i-1][j-money[i]]+value[i])
对于第i件 若买 则这样变
若不买 则不变
神奇的地方:我也不知道要不要买 但算法会帮我知道


public class Main4 {
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();//n件物品
int d=sc.nextInt();//背包大小为d
int[] value=new int[n+1];
int[] weight=new int[n+1];
for(int i=1;i<=n;i++)
{
weight[i]=sc.nextInt();
}
for(int j=1;j<=n;j++)
{
value[j]=sc.nextInt();
}
//dp[i][x]表示背包大小为x时前i件的最大价值,
//对于dp[i][j]=max{dp[i-1][j-weight[i]]+value[i],dp[i-1][j]}
//买第i件或者不买,算法帮我决定吧
int[][] dp=new int[n+1][d+1];
dp[0][d]=0;
for(int i=1;i<=n;i++)
{
for(int j=d;j>=weight[i];j--)
{
dp[i][j]=Integer.max(dp[i-1][j],dp[i-1][j-weight[i]]+value[i]);
}
}
System.out.println(dp[n][d]);
}
}

试着像这样列个表格 自己手动推下 就逐渐明白了

(1)dp[i][j] 字符串s1前i个字符 字符串s2前j个字符 替换最小的步骤
(2)IF(S1[i]==s2[j]) 假如两个字母相同 我们让他俩匹配
或者不匹配 把s1[i]i删除了
或者在s1[i]前插入s2[j]
dp[i][j]=min{dp[i-1][j]+1,dp[i-1][j-1],dp[i][j-1]+1}
IF(S1[i]!=s2[j]) 假如两个字母不同 我们让s1【i】替换
或者把s1【i】删除了
或者把在s1【i】前插入s2【j】
dp[i][j]=min{dp[i-1][j-1]+1,dp[i-1][j]+1,dp[i][j-1]+1}
(3)public int minDistance(String word1, String word2) {
//dp[i][j]表示 字符串1 i索引前 与字符串2 j索引前 最少的操作数 (注意本题是对word1进行操作)
// if(s1[i]==s2[j])两个字母相等的话 可以相互匹配
// 也可以不相互匹配 如horse 和 seeh 若h与h相匹配则 会使操作数变得很大 (匹配或把s1[i]删除,
//或者把后面插入一个一样的)
//dp[i][j]=min(dp[i-1][j-1],dp[i-1][j]+1,dp[i][j-1]+1)
//else if(s1[i]!=s2[j])
//删除 替换 插入
//dp[i][j]=min(dp[i-1][j]+1,dp[i-1][j-1]+1,dp[i][j-1]+1)
int n1=word1.length();
int n2=word2.length();
int[][] dp=new int[n1+1][n2+1];
for(int i=0;i<=n1;i++)
{
dp[0][i]=i;
dp[i][0]=i;
}
for(int i=1;i<=n1;i++)
{
for(int j=1;j<=n2;j++)
{
if(word1.charAt(i-1)==word2.charAt(j-1))
{
dp[i][j]=Integer.min(Integer.min(dp[i-1][j-1], dp[i-1][j]+1), dp[i][j-1]+1);
}
else
{
dp[i][j]=Integer.min(Integer.min(dp[i-1][j]+1, dp[i-1][j-1]+1), dp[i][j-1]+1);
}
}
}
return dp[n1][n2];
}

(放心,上面及下面代码都全部通过全部用例了)


(1) dp[i][j] 表示前j个被戳了i个气球 的钱数
(2)我们若不戳第j个气球
我们戳第j个气球
dp[i][j]=max{dp[i][j-1],dp[i-1][j-1]+money[j]*money[j-1]*money[j+1]}

(1)dp[i][j]表示 到坐标【i】【j】的不同路径数
(2)可以由左边那块过来 由上面那块过来
dp[i][j]=dp[i-1][j]+dp[i][j-1]
(3)
class Solution {
public int uniquePaths(int m, int n) {
//dp[i][j]表示到(i,j)有多少种不同的方式
//dp[i][j]=dp[i-1][j]+dp[i-1][j-1]+dp[i][j-1](可能 左边 上边到达该点)
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<m;i++)
{
for(int j=1;j<n;j++)
{
dp[i][j]=dp[i-1][j]+dp[i][j-1];
}
}
return dp[m-1][n-1];
}
}



(1)dp[i][j] 表示到坐标为i,j的不同路径数
(2)从i j来 可以由上面来 或者左边来
但当在障碍物的下方或者右方时 就只有一种来的方式了
if(i,j在障碍物的右边)
dp[i][j]=dp[i][j-1]
else if(i,j在障碍物的下边)
dp[i][j]=dp[i-1][j]
else

dp[i][j]=dp[i-1][j]+dp[i][j-1]
(3)
public int uniquePathsWithObstacles(int[][] map) {
//dp[i][j]表示到(i,j)有多少种走法
//if(map[i-1][j]==0&&map[i][j-1]==0) 左边和上面都没有障碍物
//dp[i][j]=dp[i-1][j]+dp[i][j-1]
//else if(map[i-1][j]==1&&map[i][j-1]==0) 上面有障碍物 左边没有障碍物
//dp[i][j]=dp[i][j-1]
//else if(map[i-1][j]==1&&map[i][j-1]==0) 左边有障碍物 上面有障碍物
//dp[i][j]=dp[i-1][j]
//else if(map[i-1][j]==0&&map[i][j-1]==0) 左边没有障碍物 上面没有障碍物
//dp[i][j]=0
int m=map.length;//竖
int n=map[0].length;//横 dp[竖][横]
int [][]dp=new int[m][n];
for(int i=0;i<m&&map[i][0]==0;i++)
{
dp[i][0]=1;
}
for(int i=0;i<n&&map[0][i]==0;i++)
{
dp[0][i]=1;
}
for(int i=1;i<m;i++)
for(int j=1;j<n;j++)
{
if(map[i][j]==1)
{
dp[i][j]=0;
continue;
}
if(map[i-1][j]==0&&map[i][j-1]==0)
{
dp[i][j]=dp[i-1][j]+dp[i][j-1];
}
else if(map[i-1][j]==1&&map[i][j-1]==0)
{
dp[i][j]=dp[i][j-1];
}
else if(map[i-1][j]==0&&map[i][j-1]==1)
{
dp[i][j]=dp[i-1][j];
}
else if(map[i-1][j]==1&&map[i][j-1]==1)
{
dp[i][j]=0;
}
}
return dp[m-1][n-1];
}

到此时 例题已经结束了!!随博主一起去练5道把 都做出来就动态规划算作掌握了!!
(leetcode 选标签动态规划的题 选5道 自己独立思考哦 不会的话去看下题解)
再来五道!!!!!


(1)f[x]表示以序列x结尾的摆动序列最长长度(这种状态的设置借鉴了最长递增子序列)
(2)f[i]=max{ numl[1]表示下个数要增 numl【-1】表示下个数要减
numl【0】表示下个数可增可减
//if(numl【j】==1&&num[i]>numl[j]) f[j]+1
//else if(numl【j】==-1&&num[i]<numl[j]) f[j]+1
//else if(numl[j]=0) f[j]+1 } 记得更新numl
(3)
public int wiggleMaxLength(int[] nums) {
//f[x]表示以序列x结尾的摆动序列最长长度
//numl[]=1表示下一个数该增减 -1表示下一个数该减少
//f[i]=max{
//if(numl【j】==1&&num[i]>numl[j]) f[j]+1
//else if(numl【j】==-1&&num[i]<numl[j]) f[j]+1
//else if(numl[j]=0) f[j]+1 记得更新numl
int n=nums.length;
if(n==0)
return 0;
int[] numl=new int[n];
numl[0]=0;
int[] f=new int[n];
f[0]=1;
for(int i=1;i<n;i++)
{
int max=0;
for(int j=i-1;j>=0;j--)
{
if(f[j]+1>max)
{
if(numl[j]==0&&nums[i]!=nums[j])
{
max=f[j]+1;
if(nums[i]>nums[j])
{
numl[i]=-1;
}
else {
numl[i]=1;
}
}
else if(numl[j]==1&&nums[i]>nums[j])
{
max=f[j]+1;
numl[i]=-1;
}
else if(numl[j]==-1&&nums[i]<nums[j])
{
max=f[j]+1;
numl[i]=1;
}
}
}
f[i]=max;
}
Arrays.sort(f);
return f[n-1];
}


(1)dp[i][j]表示s前 i位是否是t前j位的子序列
(2)if(s[i]==t[j])
dp[i][j]=dp[i-1][j-1]
else if(s[i]!=t[j])
dp[i][j]=dp[i][j-1]
(3) public boolean isSubsequence(String s, String t) {
//dp[i][j]表示s前 i位是否是t前j位的子序列
//if(s[i]==t[j])
// dp[i][j]=dp[i-1][j-1]
//else if(s[i]!=t[j])
// dp[i][j]=dp[i][j-1]
int m=s.length();
int n=t.length();
int[][] dp=new int[m+1][n+1];
for(int i=0;i<=m;i++) dp[i][0]=0;
for(int i=0;i<=n;i++) dp[0][i]=1;
for(int i=1;i<=m;i++)
{
for(int j=1;j<=n;j++)
{
if(s.charAt(i-1)==t.charAt(j-1))
dp[i][j]=dp[i-1][j-1];
else
dp[i][j]=dp[i][j-1];
}
}
if(dp[m][n]==1)
return true;
else
return false;
}

(没办法 动态规划法解这道题 等于屠龙刀杀鸡)

有4种 (顺序不一样 但数字一样算一种) 1111 112 22 13
(1)dp[i][j] 表示用序列 i前的包括序列i的数字组成j有多少种方式(nums序列假设从1开始)
(2)dp[i][j]=dp[i-1][j-k*nums[i](剩余的数满足不了nums[i])]+...+dp[i-1][j-nums[i]]+dp[i][j]
(3)public static int combinationSum4(int[] nums, int target) {
//dp[i][j] 表示用序列 i前的包括序列i的数字组成j有多少种方式(nums序列假设从1开始)
//dp[i][j]=dp[i-1][j-k*nums[i](剩余的数满足不了nums[i])]+...+dp[i-1][j-nums[i]]+dp[i][j]
int n=nums.length;
int[][] dp=new int[n+1][target+1];
for(int i=0;i<=n;i++)
{
dp[i][0]=1;
}
for(int i=1;i<=n;i++)
{
for(int j=target;j>=1;j--)
{
int k=j/nums[i-1];
for(int t=0;t<=k;t++)
{
dp[i][j]=dp[i][j]+dp[i-1][j-t*nums[i-1]];
}
}
}
return dp[n][target]
}

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容,请联系我们,一经查实,本站将立刻删除。
如需转载请保留出处:https://51itzy.com/kjqy/131730.html