leetcode 1547. Minimum Cost to Cut a Stick 区间dp

题目

https://leetcode.com/problems/minimum-cost-to-cut-a-stick/
Given a wooden stick of length n units. The stick is labelled from 0 to n. For example, a stick of length 6 is labelled as follows:

Given an integer array cuts where cuts[i] denotes a position you should perform a cut at.

You should perform the cuts in order, you can change the order of the cuts as you wish.

The cost of one cut is the length of the stick to be cut, the total cost is the sum of costs of all cuts. When you cut a stick, it will be split into two smaller sticks (i.e. the sum of their lengths is the length of the stick before the cut). Please refer to the first example for a better explanation.

Return the minimum total cost of the cuts.

Example 1:

Input: n = 7, cuts = [1,3,4,5]
Output: 16
Explanation: Using cuts order = [1, 3, 4, 5] as in the input leads to the following scenario:

The first cut is done to a rod of length 7 so the cost is 7. The second cut is done to a rod of length 6 (i.e. the second part of the first cut), the third is done to a rod of length 4 and the last cut is to a rod of length 3. The total cost is 7 + 6 + 4 + 3 = 20.
Rearranging the cuts to be [3, 5, 1, 4] for example will lead to a scenario with total cost = 16 (as shown in the example photo 7 + 4 + 3 + 2 = 16).
Example 2:

Input: n = 9, cuts = [5,6,1,4,2]
Output: 22
Explanation: If you try the given cuts ordering the cost will be 25.
There are much ordering with total cost <= 25, for example, the order [4, 6, 5, 2, 1] has total cost = 22 which is the minimum possible.

Constraints:

2 <= n <= 10^6
1 <= cuts.length <= min(n – 1, 100)
1 <= cuts[i] <= n – 1
All the integers in cuts array are distinct.

思路

1000 题合并石堆还简单,是 K = 2 的特殊情况,直接区间 dp AC,参考矩阵乘法结合律优化
cuts 数组直接作为向前累加和,注意排序

源码

class Solution {
public:;
    ;
    int minCost(int n, vector<int>& cuts) {
        cuts.push_back(n);
        sort(begin(cuts),end(cuts));
        vector<vector<int>> dp(cuts.size()+1,vector<int>(cuts.size()+1,INT_MAX));  
        return calDp(0,cuts.size()-1,cuts,dp);
    }
    int calDp(int i,int j,vector<int>& cuts,vector<vector<int>>&dp){
        if(dp[i][j] != INT_MAX){
            return dp[i][j];
        }
        if(i == j){
           return dp[i][j] = 0;
        }else if(i+1 == j){
           return dp[i][j] = cuts[j]-(i==0?0:cuts[i-1]);
        }else{
            for(int k = i;k < j;++k){
                dp[i][j]=min(dp[i][j],calDp(i,k,cuts,dp)+calDp(k+1,j,cuts,dp)+cuts[j]-(i==0?0:cuts[i-1]));
            }
        }
        return dp[i][j];
    }
};

leetcode 1000. Minimum Cost to Merge Stones 区间dp 归并

题目

https://leetcode.com/problems/minimum-cost-to-merge-stones/
There are N piles of stones arranged in a row. The i-th pile has stones[i] stones.

A move consists of merging exactly K consecutive piles into one pile, and the cost of this move is equal to the total number of stones in these K piles.

Find the minimum cost to merge all piles of stones into one pile. If it is impossible, return -1.

Example 1:

Input: stones = [3,2,4,1], K = 2
Output: 20
Explanation:
We start with [3, 2, 4, 1].
We merge [3, 2] for a cost of 5, and we are left with [5, 4, 1].
We merge [4, 1] for a cost of 5, and we are left with [5, 5].
We merge [5, 5] for a cost of 10, and we are left with [10].
The total cost was 20, and this is the minimum possible.
Example 2:

Input: stones = [3,2,4,1], K = 3
Output: -1
Explanation: After any merge operation, there are 2 piles left, and we can’t merge anymore. So the task is impossible.
Example 3:

Input: stones = [3,5,1,2,6], K = 3
Output: 25
Explanation:
We start with [3, 5, 1, 2, 6].
We merge [5, 1, 2] for a cost of 8, and we are left with [3, 8, 6].
We merge [3, 8, 6] for a cost of 17, and we are left with [17].
The total cost was 25, and this is the minimum possible.

Note:

1 <= stones.length <= 30
2 <= K <= 30
1 <= stones[i] <= 100

思路

区间 dp
子问题划分要把 [i,j] 范围内的石堆合并成 k 个石堆,需要考虑从 t 开始,[i,t] 合并成一个石堆,[t+1,j] 合并成 k-1 个石堆,t 的步长为 K-1,边界条件为 i == j

源码

class Solution {
public:
    vector<vector<vector<long>>> dp;
    vector<int> pre;
    int DK;
    int mergeStones(vector<int>& stones, int K) {
        DK = K;
        dp.resize(stones.size()+1,vector<vector<long>>(stones.size()+1,vector<long>(K+1,INT_MAX)));
        pre.resize(stones.size()+1,0);
        for(int i = 0;i < stones.size();++i){
            pre[i]=pre[i==0?0:i-1]+stones[i];
        }
        return calDp(0,stones.size()-1,1)==INT_MAX?-1:calDp(0,stones.size()-1,1);
    }
    long calDp(int st,int ed,int k){
        if(dp[st][ed][k]!=INT_MAX)return dp[st][ed][k];
        if(st==ed){
            return dp[st][ed][k] = k==1?0:INT_MAX;
        }
        if((ed-st-k+1)%(DK-1)!=0){
            return dp[st][ed][k] = INT_MAX;
        }
        if(k == 1){
            return dp[st][ed][1] = calDp(st,ed,DK)+pre[ed]-(st==0?0:pre[st-1]);
        }
        for(int t = st;t < ed;t += (DK-1)){
            dp[st][ed][k] = min(dp[st][ed][k],calDp(st,t,1)+calDp(t+1,ed,k-1));
        }
        return dp[st][ed][k];
    }
};

leetcode 1546. Maximum Number of Non-Overlapping Subarrays With Sum Equals Target 动态规划 向前累积和

题目

https://leetcode.com/contest/weekly-contest-201/problems/maximum-number-of-non-overlapping-subarrays-with-sum-equals-target/
Given an array nums and an integer target.

Return the maximum number of non-empty non-overlapping subarrays such that the sum of values in each subarray is equal to target.

Example 1:

Input: nums = [1,1,1,1,1], target = 2
Output: 2
Explanation: There are 2 non-overlapping subarrays [1,1,1,1,1] with sum equals to target(2).
Example 2:

Input: nums = [-1,3,5,1,4,2,-9], target = 6
Output: 2
Explanation: There are 3 subarrays with sum equal to 6.
([5,1], [4,2], [3,5,1,4,2,-9]) but only the first 2 are non-overlapping.
Example 3:

Input: nums = [-2,6,6,3,5,4,1,2,8], target = 10
Output: 3
Example 4:

Input: nums = [0,0,0], target = 0
Output: 3

Constraints:

1 <= nums.length <= 10^5
-10^4 <= nums[i] <= 10^4
0 <= target <= 10^6

思路

记录累计和,同时每次只需要找 s[i] – target 的位置,然后max(dp+1,dp),即分别对应是否选择第 i 位,其中寻找 s[i]-target 时,从后向前找,第一个命中即可,因为dp[i+1]>=dp[i],即数组越长,则值一定越大,所以贪心保证选择i后的子序列最短即可。
为了提高效率,使用map记录,其中为了避免保证找到的索引一定小于i,在更新dp后再更新map

源码

class Solution {
public:
    vector<int> dp,s;
    map<int,int> m;
    int maxNonOverlapping(vector<int>& nums, int target) {
        dp.resize(nums.size()+1,0);
        s.resize(nums.size()+1,0);
        int sum = 0;

        for(int i = 0;i<nums.size();++i){
            sum+=nums[i];
            s[i]=sum;

            dp[i] = dp[i==0?0:i-1];
            if(nums[i]==target){ 
                dp[i]++;
                cout<<"a "<<i<<" "<<dp[i]<<endl;
                m[sum] = i;
                continue;
            }
            if(m.count(s[i]-target)!=0){
                dp[i]=max(dp[i],dp[m[s[i]-target]]+1);
                cout<<"b "<<i<<" "<<dp[i]<<endl;
            }else if(s[i]==target){
                dp[i]=max(dp[i],1);
                cout<<"c "<<i<<" "<<dp[i]<<endl;
            }
             m[sum] = i;

        }
        return dp[nums.size()-1];
    }
};

4.5算法之动态规划 193:棋盘分割 区间dp

题目

http://noi.openjudge.cn/ch0405/193/
描述
将一个8*8的棋盘进行如下分割:将原棋盘割下一块矩形棋盘并使剩下部分也是矩形,再将剩下的部分继续如此分割,这样割了(n-1)次后,连同最后剩下的矩形棋盘共有n块矩形棋盘。(每次切割都只能沿着棋盘格子的边进行)

原棋盘上每一格有一个分值,一块矩形棋盘的总分为其所含各格分值之和。现在需要把棋盘按上述规则分割成n块矩形棋盘,并使各矩形棋盘总分的均方差最小。
均方差,其中平均值,xi为第i块矩形棋盘的总分。
请编程对给出的棋盘及n,求出O’的最小值。
输入
第1行为一个整数n(1 < n < 15)。
第2行至第9行每行为8个小于100的非负整数,表示棋盘上相应格子的分值。每行相邻两数之间用一个空格分隔。
输出
仅一个数,为O’(四舍五入精确到小数点后三位)。

思路

区间 dp, dp[k][x1][y1][x2][y2] 表示将,(x1,y1):(x2,y2)区间内的矩形分成 k 块,均方误差的最小值
该问题是一个一对多问题,即两个子矩形的最优解拼接为一个大矩形后不一定为最优解,但是一个大矩形的最优解一定可以由两个子矩形的解拼接而成,所以针对子矩形遍历其横向划分和纵向划分。

其中要最小化平方和即可,具体推导过程参考该博客
https://blog.csdn.net/nnnnnnnnnnnny/article/details/51592665

源码

//
//  193.cpp
//  test
//
//  Created by sgxm on 2020/8/3.
//  Copyright © 2020 sgxm. All rights reserved.
//

#include <stdio.h>
#include <iostream>
#include <math.h>
#include <memory.h>
#include <iomanip>
#include <string.h>
#define maxn 15
using namespace std;

int dp[15][8][8][8][8];
int s[8][8][8][8];
int tb[8][8];
int n;
int calSum(int x1,int y1,int x2,int y2){
    int sum = 0;
    for(int i = x1;i<=x2;++i){
        for(int j = y1;j <= y2;++j){
            sum+=tb[i][j];
        }
    }
    return sum*sum;
}
int calDp(int k,int x1,int y1,int x2,int y2){
    int MIN = 99999999;

    if(dp[k][x1][y1][x2][y2]!=-1){
        return dp[k][x1][y1][x2][y2];
    }
    if(k == 1){
        return dp[k][x1][y1][x2][y2]=s[x1][y1][x2][y2];
    }
    dp[k][x1][y1][x2][y2]=MIN;
    //横向划分
    for(int x = x1;x<x2;++x){
        int t1 = calDp(k-1, x1, y1, x, y2);
        int t2 = calDp(k-1,x+1,y1,x2,y2);
        int t = min(t1+s[x+1][y1][x2][y2],t2+s[x1][y1][x][y2]);
        MIN = min(MIN,t);
    }
    for(int y = y1;y<y2;++y){
        int t1 = calDp(k-1,x1,y1,x2,y);
        int t2 = calDp(k-1,x1,y+1, x2, y2);
        int t = min(t1+s[x1][y+1][x2][y2],t2+s[x1][y1][x2][y]);
        MIN = min(MIN,t);
    }
    MIN=min(MIN,dp[k][x1][y1][x2][y2]);
    //cout<<k<< " "<<x1<<" "<<y1<<" "<<x2<<" "<<y2<<" = "<<MIN<<endl;
    return  dp[k][x1][y1][x2][y2]=MIN;

}
int main(){
    cin >> n;
    for(int i = 0;i < 8;++i){
        for(int j = 0;j < 8;++j){
            cin >> tb[i][j];
        }
    }
    memset(dp, -1,sizeof(dp));
    //init Sum
    for(int x1 = 0;x1 < 8;++x1){
        for(int y1 = 0;y1 < 8;++y1){
            for(int x2 = x1;x2<8;++x2){
                for(int y2 = y1;y2<8;++y2){
                    s[x1][y1][x2][y2]=calSum(x1,y1,x2,y2);
                }
            }
        }
    }
    //calDp(2,5,5,6,7);
    int sum2 = calDp(n, 0, 0, 7, 7);
    double res = 1.0*n*calDp(n, 0, 0, 7, 7)-s[0][0][7][7];
    cout<<setiosflags(ios::fixed)<<setprecision(3)<<sqrt(res/(n*n))<<endl;
    return 0;
}

4.5算法之动态规划 191:钉子和小球 概率

题目

http://noi.openjudge.cn/ch0405/191/
描述
有一个三角形木板,竖直立放,上面钉着n(n+1)/2颗钉子,还有(n+1)个格子(当n=5时如图1)。每颗钉子和周围的钉子的距离都等于d,每个格子的宽度也都等于d,且除了最左端和最右端的格子外每个格子都正对着最下面一排钉子的间隙。
让一个直径略小于d的小球中心正对着最上面的钉子在板上自由滚落,小球每碰到一个钉子都可能落向左边或右边(概率各1/2),且球的中心还会正对着下一颗将要碰上的钉子。例如图2就是小球一条可能的路径。
我们知道小球落在第i个格子中的概率pi=,其中i为格子的编号,从左至右依次为0,1,…,n。
现在的问题是计算拔掉某些钉子后,小球落在编号为m的格子中的概率pm。假定最下面一排钉子不会被拔掉。例如图3是某些钉子被拔掉后小球一条可能的路径。

输入
第1行为整数n(2 <= n <= 50)和m(0 <= m <= n)。以下n行依次为木板上从上至下n行钉子的信息,每行中’*’表示钉子还在,’.’表示钉子被拔去,注意在这n行中空格符可能出现在任何位置。
输出
仅一行,是一个既约分数(0写成0/1),为小球落在编号为m的格子中的概pm。既约分数的定义:A/B是既约分数,当且仅当A、B为正整数且A和B没有大于1的公因子。

思路

n = 2 时,第 0 层为钉子的上一层,初始小球 2^n
从第 0 层开始,第一个钉子编号为 1,第一个坑位编号为 0,对于每一个坑位考虑
– 其上方钉子空则上两层对应小球数量直接累加
– 左侧钉子不空则左侧钉子上方小球数量一半累加到该位置
– 右侧同理

最后辗转相除法求最大公约数,约分

源码

//
//  191.cpp
//  test
//
//  Created by bytedance on 2020/7/30.
//  Copyright © 2020 bytedance. All rights reserved.
//

#include <stdio.h>
#include <iostream>
#include <vector>
#include <math.h>
using namespace std;
vector<vector<long long>> dp;
vector<vector<char>> cnt;
long long gcd(long long x,long long y){
    return y?gcd(y,x%y):x;
}
int main(){
    long long n,m;
    cin >> n >> m;
    cnt.resize(n+1,vector<char>(n+1));
    dp.resize(n+1,vector<long long>(n+1,0));
    for(long long i = 1;i <= n; ++i){
        for(long long j = 1;j <= i; ++j){
            char c;
            cin >> c;
            cnt[i][j]=c;
        }
    }
    //
    dp[0][0] = pow(2,n);
    for(long long i = 1;i <= n;++i){
        for(long long j = 0;j <= i; ++j){
            //处理左右边界
            if(j == 0){
                if(cnt[i][j+1]=='*'){
                    dp[i][j]=dp[i-1][j]/2;
                }else{
                    dp[i][j]=0;
                }
            }else if(j == i){
                if(cnt[i][j]=='*'){
                    dp[i][j]=dp[i-1][j-1]/2;
                }else{
                    dp[i][j]=0;
                }
            }else{
                if(cnt[i-1][j]=='.'){
                    dp[i][j]+=dp[i-2][j-1];
                }
                if(cnt[i][j]=='*'){
                    dp[i][j]+=dp[i-1][j-1]/2;
                }
                if(cnt[i][j+1]=='*'){
                    dp[i][j]+=dp[i-1][j]/2;
                }
            }
        }
    }

    long long a = dp[n][m],b = dp[0][0];
    long long gc=gcd(b,a);
    a/=gc;
    b/=gc;
    cout << a<<"/"<<b;

    return 0;
}

4.5算法之动态规划 1249:Humble Numbers 优先级队列

http://noi.openjudge.cn/ch0405/1249/

思路

取出队头,遍历乘四放入队列,即可保证当前队头为最小值

源码

//
//  1249.cpp
//  test
//
//  Created by bytedance on 2020/7/28.
//  Copyright © 2020 bytedance. All rights reserved.
//

#include <stdio.h>
#include <iostream>
#include <vector>
#include <queue>

using namespace std;
int m[4]={2,3,5,7};
priority_queue<long long,vector<long long>,greater<long long>> q;
int main(){
    q.push(1);
    int idx = 0;
    int i;
    long long pre = 0;
    while(cin >> i){
        if(i == 0){
            break;
        }

        while(idx<i){
            while(q.top()==pre){
                q.pop();
            }
            pre = q.top();
            idx++;
            for(int i = 0;i < 4;++i){
                q.push(pre*m[i]);
            }
        }
        if(i%100>=10&&i%100<=20)
            printf("The %dth humble number is %lld.\n",i,pre);
        else if(i%10==1)
            printf("The %dst humble number is %lld.\n",i,pre);
        else if(i%10==2)
            printf("The %dnd humble number is %lld.\n",i,pre);
        else if(i%10==3)
            printf("The %drd humble number is %lld.\n",i,pre);
        else
            printf("The %dth humble number is %lld.\n",i,pre);
    }
    return 0;
}