# 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 .
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 .
The total cost was 25, and this is the minimum possible.

Note:

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

#### 源码

``````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] = 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

#### 源码

``````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/

#### 思路

https://blog.csdn.net/nnnnnnnnnnnny/article/details/51592665

#### 源码

``````//
//  193.cpp
//  test
//
//  Created by sgxm on 2020/8/3.
//

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

int dp;
int s;
int tb;
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;
cout<<setiosflags(ios::fixed)<<setprecision(3)<<sqrt(res/(n*n))<<endl;
return 0;
}

``````

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

#### 题目

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

#### 思路

n = 2 时，第 0 层为钉子的上一层，初始小球 – 其上方钉子空则上两层对应小球数量直接累加
– 左侧钉子不空则左侧钉子上方小球数量一半累加到该位置
– 右侧同理

#### 源码

``````//
//  191.cpp
//  test
//
//  Created by bytedance on 2020/7/30.
//

#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 = 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;
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.
//

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

using namespace std;
int m={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;
}

``````