数位成本和为目标值的最大数字
class Solution {
public String largestNumber(int[] cost,int target){
//完全背包问题
int n=cost.length;
int[][] dp=new int[10][target+1];
//初始化
for(int i=0;i<10;i++){
Arrays.fill(dp[i],Integer.MIN_VALUE);
}
dp[0][0]=0;
//定义状态转移
int[][] from=new int[10][target+1];
for(int i=0;i<9;i++){
int c=cost[i];
for(int j=0;j<=target;j++){
if (c > j) {
//不能选
dp[i+1][j]=dp[i][j];
from[i+1][j]=j;//没有选
}else{
//可以选
if(dp[i][j]>dp[i+1][j-c]+1){
dp[i+1][j]=dp[i][j];
from[i+1][j]=j;
}else{
dp[i+1][j]=dp[i+1][j-c]+1;
from[i+1][j]=j-c;
}
}
}
}
if(dp[9][target]<0){
return "0";
}
StringBuilder sb=new StringBuilder();
int i=9;int j=target;
while(j>0){
if(j==from[i][j]){
i--;
}else{
sb.append(i);
j=from[i][j];
}
}
return sb.toString();
}
}
DI序列的有效排列
class Solution {
public int numPermsDISequence(String s){
int n=s.length();
int MOD=1000000007;int res=0;
int[][] dp=new int[n+1][n+1];
dp[0][0]=1;
//s[i-1]=='D' :dp[i][j]=dp[i-1][j]+dp[i-1][j+1]+dp[i-1][j+2]+...+dp[i-1][i-1]
//s[i-1]=='I' :dp[i][j]=dp[i-1][0]+dp[i-1][1]+dp[i-1][2]+...+dp[i-1][j-1]
for(int i=1;i<=n;i++){
for(int j=0;j<=i;j++){
if(s.charAt(i-1)=='D'){
for(int k=j;k<i;k++){
dp[i][j]=(dp[i][j]+dp[i-1][k])%MOD;
}
}else{
for(int k=0;k<j;k++){
dp[i][j]=(dp[i][j]+dp[i-1][k])%MOD;
}
}
}
}
for(int i=0;i<=n;i++){
res=(res+dp[n][i])%MOD;
}
return res;
}
}
盈利计划
盈利计划
多维度背包问题 定义dp[i][j][k]表示前i项任务,人数<=j;利润>=k的所有的方案数
j不能够为负数,所以对于第i项任务是否选择通过j控制,方案数
class Solution {
public int profitableSchemes(int n, int minProfit, int[] group, int[] profit) {
int MOD=1000000007;
int k=profit.length;
int[][][] dp=new int[k+1][n+1][minProfit+1];
//对于没有安排任务对应的方案数只有1种
for(int i=0;i<=n;i++){
dp[0][i][0]=1;
}
for(int i=1;i<=k;i++){
int members=group[i-1];
int profits=profit[i-1];
for(int j=0;j<=n;j++){
for(int t=0;t<=minProfit;t++){
if (j < members) {
//不能选第i任务
dp[i][j][t]=dp[i-1][j][t]%MOD;
}else{
//可以选第i项任务
dp[i][j][t]=(dp[i-1][j][t]+dp[i-1][j-members][Math.max(t-profits,0)])%MOD;
}
}
}
}
return dp[k][n][minProfit]%MOD;
}
}
最低加油次数
最低加油次数
方式一:通过dp[i][j]:表示前i个加油站,加了j次油,对于第i个加油站,状态转移分两种:
(1)第i个加油站没有加油
(2)第i个加油站加油
class Solution {
//最低加油次数
//dp[i][j]:表示前i个加油站,加油次数为j
public int minRefuelStops(int target, int startFuel, int[][] stations) {
int n=stations.length;
int[][] dp=new int[n+1][n+1];
for(int i=0;i<=n;i++){
dp[i][0]=startFuel;
}
for(int i=1;i<=n;i++){
for(int j=1;j<=i;j++){
//如果第i个加油站不加油
if(dp[i-1][j]>=stations[i-1][0]){
dp[i][j]=dp[i-1][j];
}
//第i个加油站加油
if(dp[i-1][j-1]>=stations[i-1][0]){
dp[i][j]=Math.max(dp[i][j],dp[i-1][j-1]+stations[i-1][1]);
}
}
}
for(int i=0;i<=n;i++){
if(dp[n][i]>=target){
return i;
}
}
return -1;
}
}
方式二
通过堆优化
先走过所有的加油站
class Solution {
public int minRefuelStops(int target, int startFuel, int[][] stations) {
//每一次并不是立刻加油,当没有油的时候,选择之前最多的油开始加
int res=0;
PriorityQueue<Integer> queue=new PriorityQueue<Integer>(Collections.reverseOrder());
int prev=0;
for (int[] station : stations) {
int location=station[0];
int capacity=station[1];
startFuel-=(location-prev);
while (startFuel < 0 && !queue.isEmpty()) {
startFuel+=queue.poll();
res++;
}
//加不满
if(startFuel<0){
return -1;
}
queue.offer(capacity);
prev=location;
}
//走完所有的加油站
startFuel-=(target-prev);
while (startFuel < 0 && !queue.isEmpty()) {
startFuel+=queue.poll();
res++;
}
if (startFuel < 0) {
return -1;
}
return res;
}
}
播放列表的数量
播放列表的数量
dp[i][j]表示前i首歌有j首不同的歌
class Solution {
public int numMusicPlaylists(int n, int goal, int k) {
int MOD=1000000007;
long[][] dp=new long[goal+1][n+1];//dp[i][j]表示前i首歌,有j首不相同的歌
dp[0][0]=1;
for(int i=1;i<=goal;i++){
for(int j=1;j<=n&&j<=i;j++){
dp[i][j]=(1L*dp[i-1][j-1]*(n-j+1)+1L*dp[i-1][j]*(Math.max(0,j-k)))%MOD;
}
}
return (int)dp[goal][n];
}
}
工作计划的最低难度
工作计划最低难度
将对应的数组分成d组,使得每一组最大值之和最小
class Solution {
public int minDifficulty(int[] jobDifficulty, int d) {
int n=jobDifficulty.length;
if(n<d){
return -1;
}
int[][] dp=new int[n+1][d+1];//dp[i][j]表示将前i个元素分成j组
for(int i=0;i<=n;i++){
Arrays.fill(dp[i],0x3f3f3f);
}
//类似于预处理前缀,先预处理所有区间最大值
int[][] maxv=new int[n+1][n+1];
for(int i=1;i<=n;i++){
for(int j=i;j<=n;j++){
if(i!=j){
maxv[i][j]=Math.max(maxv[i][j-1],jobDifficulty[j-1]);
}else{
maxv[i][j]=jobDifficulty[j-1];
}
}
}
//初始化
for(int i=1;i<=n;i++){
dp[i][1]=maxv[1][i];
}
for(int i=1;i<=n;i++){
for(int j=2;j<=d;j++){//分成一组已经初始化
//分界点
for(int k=1;k<i;k++){
dp[i][j]=Math.min(dp[i][j],dp[k][j-1]+maxv[k+1][i]);
}
}
}
return dp[n][d]==0x3f3f3f? -1:dp[n][d];
}
}
停在原地的方案数
将BFS搜索分支看成状态转移,将BFS改成dp求方案数
class Solution {
public int numWays(int steps,int arrLen){
int MOD=1000000007;
int m=Math.min(arrLen-1,steps);
int[][] dp=new int[steps+1][m+1];
dp[0][0]=1;
for(int i=1;i<=steps;i++){
for(int j=0;j<=m;j++){
dp[i][j]=dp[i-1][j];
if(j-1>=0){
dp[i][j]=(dp[i][j]+dp[i-1][j-1])%MOD;
}
if(j+1<=m){
dp[i][j]=(dp[i][j]+dp[i-1][j+1])%MOD;
}
}
}
return dp[steps][0];
}
}
使数组严格递增最少交换次数
使数组严格递增最少交换次数
dp[i][j][0]:前i个元素与前j个arr2元素,最后停在arr1[i-1]上
dp[i][j][1]:前i个元素与前j个arr2元素,最后停在arr3[i-1]上
class Solution {
public int makeArrayIncreasing(int[] arr1,int[] arr2){
int n=arr1.length;
Set<Integer> set=new HashSet<Integer>();
for (int i : arr2) {
set.add(i);
}
int m=set.size();
int[] arr3=new int[m];
int index=0;
Iterator it=set.iterator();
while (it.hasNext()) {
arr3[index++]=(int)it.next();
}
//将arr3排序
Arrays.sort(arr3);
int[][][] dp=new int[n+1][m+1][2];
for(int i=0;i<=n;i++){
for(int j=0;j<=m;j++){
Arrays.fill(dp[i][j],0x3f3f3f);
}
}
//初始化
for(int i=0;i<=m;i++){
dp[0][i][0]=dp[1][i][0]=0;
if(i>0){
dp[1][i][1]=1;
}
}
for(int i=2;i<=n;i++){
for(int j=1;j<=m;j++){
dp[i][j][0]=dp[i][j-1][0];
if(arr1[i-1]>arr1[i-2]){
dp[i][j][0]=Math.min(dp[i][j][0],dp[i-1][j][0]);
}
if(arr1[i-1]>arr3[j-1]){
dp[i][j][0]=Math.min(dp[i][j][0],dp[i-1][j][1]);
}
if(arr1[i-2]<arr3[j-1]){
dp[i][j][1]=Math.min(dp[i][j][1],dp[i-1][j-1][0]+1);
}
if(j>=2&&arr3[j-2]<arr3[j-1]){
dp[i][j][1]=Math.min(dp[i][j][1],dp[i-1][j-1][1]+1);
}
}
}
int res=0x3f3f3f;
for(int i=1;i<=m;i++){
res=Math.min(res,Math.min(dp[n][i][0],dp[n][i][1]));
}
return res==0x3f3f3f? -1:res;
}
}
使所有区间的异或结果为零
是所有区间的异或结果为零
class Solution {
public int minChanges(int[] nums,int k){
int n=nums.length;
int max=1024;
int[][] dp=new int[k][max];
int[] g=new int[k];
for(int i=0;i<k;i++){
Arrays.fill(dp[i],0x3f3f3f3f);
g[i]=0x3f3f3f3f;
}
for(int i=0,cnt=0;i<k;i++,cnt=0){
Map<Integer,Integer> map=new HashMap<Integer,Integer>();
for(int j=i;j<n;j+=k){
map.put(nums[j],map.getOrDefault(nums[j],0)+1);
cnt++;//每一列元素个数
}
if(i==0){
for(int xor=0;xor<max;xor++){
dp[0][xor]=Math.min(dp[0][xor],cnt-map.getOrDefault(xor,0));
g[0]=Math.min(g[0],dp[0][xor]);
}
}else{
for(int xor=0;xor<max;xor++){
dp[i][xor]=g[i-1]+cnt;
for(int cur:map.keySet()){
dp[i][xor]=Math.min(dp[i][xor],dp[i-1][xor^cur]+cnt-map.get(cur));
}
g[i]=Math.min(g[i],dp[i][xor]);
}
}
}
return dp[k-1][0];
}
}
使序列递增的最小交换次数
使序列递增的最小交换次数
定义dp[n][2]:
dp[i][0]:表示前i对数据单调递增,并且当前第i对数据没有交换
dp[i][1]:表示前i对数据单调递增,并且当前第i对数据进行了交换
class Solution {
public int minSwap(int[] nums1,int[] nums2){
//定义dp[i][0]表示前i个元素已经严格递增,并且第i个元素没有交换
int n=nums1.length;
int INF=0x3f3f3f;
int[][] dp=new int[n][2];
//将所有的元素初始化
for(int i=0;i<n;i++){
Arrays.fill(dp[i],INF);
}
dp[0][0]=0;dp[0][1]=1;
for(int i=1;i<n;i++){
if(nums1[i-1]<nums1[i]&&nums2[i-1]<nums2[i]){
dp[i][0]=Math.min(dp[i][0],dp[i-1][0]);
dp[i][1]=Math.min(dp[i][1],dp[i-1][1]+1);
}
if(nums1[i-1]<nums2[i]&&nums2[i-1]<nums1[i]){
dp[i][0]=Math.min(dp[i][0],dp[i-1][1]);
dp[i][1]=Math.min(dp[i][1],dp[i-1][0]+1);
}
}
return Math.min(dp[n-1][0],dp[n-1][1]);
}
}
可被三整除的最大和
可被三整除的最大和
dp[i][0]:前i个元素最大和余3结果为0
dp[i][1]
dp[i][2]
class Solution {
public int maxSumDivThree(int[] nums){
int n=nums.length;
int[][] dp=new int[n+1][3];
//dp[i][]:表示前i个元素
//初始化
dp[0][0]=0;dp[0][1]=Integer.MIN_VALUE;dp[0][2]=Integer.MIN_VALUE;
for(int i=1;i<=n;i++){
if(nums[i-1]%3==0){
dp[i][0]=Math.max(dp[i-1][0],dp[i-1][0]+nums[i-1]);
dp[i][1]=Math.max(dp[i-1][1],dp[i-1][1]+nums[i-1]);
dp[i][2]=Math.max(dp[i-1][2],dp[i-1][2]+nums[i-1]);
}else if(nums[i-1]%3==1){
dp[i][0]=Math.max(dp[i-1][0],dp[i-1][2]+nums[i-1]);
dp[i][1]=Math.max(dp[i-1][1],dp[i-1][0]+nums[i-1]);
dp[i][2]=Math.max(dp[i-1][2],dp[i-1][1]+nums[i-1]);
}else if(nums[i-1]%3==2){
dp[i][0]=Math.max(dp[i-1][0],dp[i-1][1]+nums[i-1]);
dp[i][1]=Math.max(dp[i-1][1],dp[i-1][2]+nums[i-1]);
dp[i][2]=Math.max(dp[i-1][2],dp[i-1][0]+nums[i-1]);
}
}
return dp[n][0];
}
}
无矛盾的最佳球队
对于通过对两个数组进行排序,一种方式是通过索引,对数组下标进行排序,参考离散化
方法三是通过将两个数组的元素进行捆绑,然后作为整体进行排序
排序规则:首先按照年龄进行排序,只要分数不冲突,选择元素个数越多越好,如果年龄相等,按照分数升序排序
但是不同年龄可能冲突,转移需要判定。如果降序排序,会出现年龄大不能转移状态
class Solution {
class Node{
int score;
int age;
public Node(int score,int age){
this.score=score;
this.age=age;
}
}
public int bestTeamScore(int[] scores,int[] ages){
List<Node> nums=new ArrayList<Node>();
int n=scores.length;
for(int i=0;i<n;i++){
nums.add(new Node(scores[i],ages[i]));
}
Collections.sort(nums,(a,b)->a.age==b.age? a.score-b.score:a.age-b.age);
int[] dp=new int[n];
for(int i=0;i<n;i++){
dp[i]=nums.get(i).score;
}
for(int i=1;i<n;i++){
for(int j=0;j<i;j++){
if(nums.get(j).score<=nums.get(i).score) {
dp[i]=Math.max(dp[i],dp[j]+nums.get(i).score);
}
}
}
int res=Integer.MIN_VALUE;
for(int i=0;i<n;i++){
res=Math.max(res,dp[i]);
}
return res;
}
}
通过索引进行排序
class Solution {
public:
int bestTeamScore(vector<int>& scores, vector<int>& ages) {
int n = scores.size();
vector<int> order(n);
for (int i = 0; i < n; ++i)
order[i] = i;
sort(order.begin(), order.end(), [&](int i, int j){
return ages[i] < ages[j] || (ages[i] == ages[j] && scores[i] < scores[j]);
});
vector<int> dp(n);
int ans = 0;
for (int i = 0; i < n; ++i) {
int idx = order[i];
dp[i] = scores[idx];
for (int j = 0; j < i; ++j) {
int last = order[j];
if (scores[last] <= scores[idx])
dp[i] = max(dp[i], dp[j] + scores[idx]);
}
ans = max(ans, dp[i]);
}
return ans;
}
};
矩阵的最大非负积
矩阵的最大非负积
positve[i][j]表示所有(0,0)到(i,j)的路径乘积的最大值
negative[i][j]表示所有(0,0)到(i,j)的路径乘积的最小值
class Solution {
public int maxProductPath(int[][] grid){
int MOD=1000000007;
int n=grid.length;int m=grid[0].length;
long[][] positive=new long[n][m];
long[][] negative=new long[n][m];
positive[0][0]=negative[0][0]=grid[0][0];
for(int i=1;i<n;i++){
positive[i][0]=negative[i][0]=positive[i-1][0]*grid[i][0];
}
for(int j=1;j<m;j++){
positive[0][j]=negative[0][j]=positive[0][j-1]*grid[0][j];
}
for(int i=1;i<n;i++){
for(int j=1;j<m;j++){
if(grid[i][j]>0){
positive[i][j]=Math.max(positive[i-1][j],positive[i][j-1])*grid[i][j];
negative[i][j]=Math.min(negative[i-1][j],negative[i][j-1])*grid[i][j];
}else if(grid[i][j]<0){
positive[i][j]=Math.min(negative[i-1][j],negative[i][j-1])*grid[i][j];
negative[i][j]=Math.max(positive[i-1][j],positive[i][j-1])*grid[i][j];
}else{
positive[i][j]=0;
negative[i][j]=0;
}
}
}
return positive[n-1][m-1]<0? -1:(int)(positive[n-1][m-1]%MOD);
}
}
乘积为正数的最长子数组长度
dp[]
positive[i]表示以nums[i]结尾的最长乘积为正数的子数组长度
negative[i]表示以nums[i]结尾的最长乘积为负数的子数组长度
如果对应的nums[i]>0:
positive[i]=positive[i-1]+1;
negative[i]=negative[i-1]>0? negative[i-1]+1:0;
如果对应的nums[i]<0:
negative[i]=positive[i-1]+1;
positive[i]=negative[i-1]>0? negative[i-1]+1:0;
如果对应的nums[i]==0:
negative[i]=0;
positive[i]=0;
class Solution {
public int getMaxLen(int[] nums){
int n=nums.length;
int[] positive=new int[n];
int[] negative=new int[n];
//初始化
if(nums[0]>0){
positive[0]=1;
}else if(nums[0]<0){
negative[0]=1;
}
int res=positive[0];
for(int i=1;i<n;i++){
if(nums[i]>0){
positive[i]=positive[i-1]+1;
negative[i]=negative[i-1]>0? negative[i-1]+1:0;
}else if(nums[i]<0){
positive[i]=negative[i-1]>0? negative[i-1]+1:0;
negative[i]=positive[i-1]+1;
}else {
positive[i]=0;
negative[i]=0;
}
res=Math.max(res,positive[i]);
}
return res;
}
}
前缀和 通过Map对前缀进行计数,通过Map进行时间优化
class Solution {
public int numOfSubarrays(int[] arr) {
//首先通过维护前缀和
int n=arr.length;
int MOD=1000000007;
int[] prefix=new int[n+1];
for(int i=0;i<n;i++){
prefix[i+1]=prefix[i]+arr[i];
}
//通过数组维护前缀奇偶元素个数
int[] dp=new int[n+1];
dp[0]=1;
for(int i=1;i<=n;i++){
dp[i]=dp[i-1]+(prefix[i]%2==0? 1:0);
}
//通过hashMap进行优化
long res=0;
Map<Integer,Integer> map=new HashMap<Integer,Integer>();
for(int i=1;i<=n;i++){
if(prefix[i]%2==0){
res=res%MOD+(i-dp[i]+1)%MOD;
}else{
res=res%MOD+dp[i]%MOD;
}
}
return (int)res%MOD;
}
}
奇偶跳
奇偶跳
通过TreeMap[HTML_REMOVED] 进行排序,默认先按照第一个关键字进行升序排序,然后按照第二关键字进行升序排序
通过ceilingKey获得第一个大于当前元素的最小的元素
floorKey()获得第一个小于当前元素的最大的元素
class Solution {
public int oddEvenJumps(int[] arr) {
int n=arr.length;
boolean[][] dp=new boolean[n][2];
//通过TreeMap进行维护对应的键值关系
TreeMap<Integer,Integer> map=new TreeMap<Integer,Integer>();
map.put(arr[n-1],n-1);
dp[n-1][0]=dp[n-1][1]=true;
int res=1;
for(int i=n-2;i>=0;i--){
Integer ceil=map.ceilingKey(arr[i]);
Integer floor=map.floorKey(arr[i]);
dp[i][0]=ceil==null? false:dp[map.get(ceil)][1];
dp[i][1]=floor==null? false:dp[map.get(floor)][0];
if(dp[i][0]){
res++;
}
map.put(arr[i],i);
}
return res;
}
}
最大的分
最大的分
交错路径进行dp,类似于将数字三角形进行变形
class Solution {
public int maxSum(int[] nums1, int[] nums2) {
//将对应的数组进行状态转移
int MOD=1000000007;
int n=nums1.length;int m=nums2.length;
long[] dp1=new long[n+1];long[] dp2=new long[m+1];
int i=0,j=0;
while(i<n&&j<m){
if(nums1[i]<nums2[j]){
dp1[i+1]=dp1[i]+nums1[i];
i++;
}else if(nums1[i]>nums2[j]){
dp2[j+1]=dp2[j]+nums2[j];
j++;
}else{
dp1[i+1]=dp2[j+1]=Math.max(dp1[i],dp2[j])+nums1[i];
i++;j++;
}
}
while(i<n){
dp1[i+1]=dp1[i]+nums1[i];
i++;
}
while(j<m){
dp2[j+1]=dp2[j]+nums2[j];
j++;
}
return (int)(Math.max(dp1[n],dp2[m])%MOD);
}
}
两个子序列的最大点积
两个子序列的最大点积
dp[i][j]表示第一个子序列的前i个元素与第二个子序列的前j个元素的最大点积
class Solution {
public int maxDotProduct(int[] nums1, int[] nums2) {
int n=nums1.length;
int m=nums2.length;
int[][] dp=new int[n][m];
//nums1[i]*nums2[j]是否构成点积,如果构成 前面的元素是否构成点积:构成:dp[i-1][j-1]+xij 前面元素如果不构成dp[i-1][j-1]
//nums1[i]与nums2[j]如果不构成点积 dp[i][j]=Math.max(dp[i][j-1],dp[i-1][j])
//综上所述:dp[i][j]=Math.max(dp[i-1][j],dp[i][j-1],dp[i-1][j-1]+xij,xij)
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
int xij=nums1[i]*nums2[j];
dp[i][j]=xij;
if(i>0){
dp[i][j]=Math.max(dp[i][j],dp[i-1][j]);
}
if(j>0){
dp[i][j]=Math.max(dp[i][j],dp[i][j-1]);
}
if(i>0&&j>0){
dp[i][j]=Math.max(dp[i-1][j-1]+xij,dp[i][j]);
}
}
}
return dp[n-1][m-1];
}
}
堆叠长方体的最大高度
class Solution {
public int maxHeight(int[][] cuboids){
int n=cuboids.length;
for (int[] cuboid : cuboids) {
Arrays.sort(cuboid);
}
//将所有的按照体积进行排序
Arrays.sort(cuboids,(a,b)->a[0]*a[1]*a[2]-b[0]*b[1]*b[2]);
int[] dp=new int[n];
int res=Integer.MIN_VALUE;
for(int i=0;i<n;i++){
for(int j=0;j<i;j++){
if(cuboids[j][0]<=cuboids[i][0]&&cuboids[j][1]<=cuboids[i][1]&&cuboids[j][2]<=cuboids[i][2]){
dp[i]=Math.max(dp[i],dp[j]);
}
}
//对于
dp[i]=dp[i]+cuboids[i][2];
res=Math.max(res,dp[i]);
}
return res;
}
}
多边形三角剖分的最低得分
class Solution {
public int minScoreTriangulation(int[] values) {
//通过dp[i][j]表示从i到j三角形剖分的最低分
int n=values.length;
int[][] dp=new int[n][n];
//dp[i][j]=min(dp[i][m]+A[i]*A[j]*A[m]+dp[m][j]),for m in range [i+1,j-1]
for(int i=n-3;i>=0;i--){
for(int j=i+2;j<n;j++){
for(int m=i+1;m<j;m++){
if(dp[i][j]==0){
dp[i][j]=values[i]*values[j]*values[m]+dp[i][m]+dp[m][j];
}else{
dp[i][j]=Math.min(dp[i][j],values[i]*values[j]*values[m]+dp[i][m]+dp[m][j]);
}
}
}
}
return dp[0][n-1];
}
}