国产无码综合区,色欲AV无码国产永久播放,无码天堂亚洲国产AV,国产日韩欧美女同一区二区

<small id="karjs"><samp id="karjs"><tbody id="karjs"></tbody></samp></small>

晴問算法動態(tài)規(guī)劃（簡單）

1年前作者：季遠(yuǎn)邇分類：Toy博客閱讀(15)違法舉報

這篇具有很好參考價值的文章主要介紹了晴問算法動態(tài)規(guī)劃（簡單）。希望對大家有所幫助。如果存在錯誤或未考慮完全的地方，請大家不吝賜教，您也可以點(diǎn)擊"舉報違法"按鈕提交疑問。

動態(tài)規(guī)劃的遞歸寫法和遞推寫法

斐波那契數(shù)列II

題目描述

給定正整數(shù)?，求斐波那契數(shù)列的第?項?(?)。

令?(?)表示斐波那契數(shù)列的第?項，它的定義是：

當(dāng)?=1時，?(?)=1；

當(dāng)?=2時，?(?)=1；

當(dāng)?>2時，?(?)=?(??1)+?(??2)。

輸入描述

一個正整數(shù)??（1≤?≤104?）。

輸出描述

斐波那契數(shù)列的第?項?(?)。

由于結(jié)果可能很大，因此將結(jié)果對10007取模后輸出。

#include <cstdio>
int fib[10001]={0};

int main() {
    int n;
    scanf("%d", &n);
    fib[1] = fib[2] = 1;
    for (int i = 3; i <= n; i++) {
        fib[i] = (fib[i - 1] + fib[i - 2])%10007;
    }
    printf("%d", fib[n]);
    return 0;
}

數(shù)塔II

題目描述

晴問算法動態(tài)規(guī)劃（簡單）,動態(tài)規(guī)劃,算法,動態(tài)規(guī)劃

數(shù)塔就是由一堆數(shù)字組成的塔狀結(jié)構(gòu)，其中第一行1個數(shù)，第二行2個數(shù)，第三行3個數(shù)，依此類推。每個數(shù)都與下一層的左下與右下兩個數(shù)相連接。這樣從塔頂?shù)剿拙涂梢杂泻芏鄺l路徑可以走，現(xiàn)在需要求路徑上的數(shù)字之和的最大值。

例如在上圖中，5->8->12->10與5->3->16->11這兩條路徑上的數(shù)字之和都是35，是所有路徑中的最大值。

輸入描述

第一行一個正整數(shù)??（1≤?≤100?），表示數(shù)塔的層數(shù)。

接下來??行為數(shù)塔從上到下的每一層，其中第??層有??個正整數(shù)，每個數(shù)都不超過1000。

輸出描述

從塔頂?shù)剿椎乃新窂街新窂缴蠑?shù)字之和的最大值。

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    int a[102][102]={0};
    cin>>n;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=i;j++){
            cin>>a[i][j];
        }
    }
    for(int i=n;i>=1;i--){
        for(int j=i;j>=1;j--){
            a[i][j]+=max(a[i+1][j],a[i+1][j+1]);
        }
    }
    cout<<a[1][1];
    return 0;
}

上樓II

題目描述

我打算走樓梯上樓，共有?級臺階。

我身輕如燕，所以每次都可以選擇上一級臺階或者兩級臺階。

問有多少種上樓的方式。

例如當(dāng)?=3時，共有三種方式上樓：

一級 => 一級 => 一級；
一級 => 二級；
二級 => 一級。

輸入描述

一個正整數(shù)??（1≤?≤104?），表示臺階級數(shù)。

輸出描述

一個整數(shù)，表示上樓的方案數(shù)。

由于結(jié)果可能很大，因此將結(jié)果對10007取模后輸出。

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin>>n;
    int a[100001];
    a[1]=1;
    a[2]=2;
    for (int i = 3; i <= n; i++) {
        a[i] = (a[i - 1] + a[i - 2])%10007;
    }  
    cout<<a[n];
    return 0; 
}

最大連續(xù)子序列和

最大連續(xù)子序列和

題目描述

現(xiàn)有一個整數(shù)序列?1,?2,...,?????，求連續(xù)子序列??+...+?????的最大值。

輸入描述

第一行一個正整數(shù)???（1≤?≤104??），表示序列長度；

第二行為用空格隔開的??個整數(shù)???（?105≤??≤105??），表示序列元素。

輸出描述

輸出一個整數(shù)，表示最大連續(xù)子序列和。

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    int a,b;
    int max1=-2222222;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a;
        if(i==1) b=a;
        else b=max(a,a+b);
        max1=max(max1,b);

    }
    cout<<max1;
    return 0;

}

最長不下降子序列（LIS）

最長上升子序列

題目描述

現(xiàn)有一個整數(shù)序列?1,?2,...,????????，求最長的子序列（可以不連續(xù)），使得這個子序列中的元素是非遞減的。輸出該最大長度。

輸入描述

第一行一個正整數(shù)?????（1≤?≤100????），表示序列長度；

第二行為用空格隔開的??個整數(shù)???（?105≤??≤105??），表示序列元素。

輸出描述

輸出一個整數(shù)，表示最大長度。

#include<iostream>
using namespace std;
int main()
{
	int n;
	cin>>n;
	int a[1001]={0};
	int dp[1001]={0};
	int maxn=0;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		dp[i]=1;
		for(int j=1;j<i;j++){
			if(a[j]<=a[i]){
				dp[i]=max(dp[i],dp[j]+1);
				
			}

		}
		if(dp[i]>maxn) maxn=dp[i];
	}
	cout<<maxn;
	return 0;
}

最長公共子序列（LCS）

最長公共子序列

題目描述

現(xiàn)有兩個字符串?1????與?2?，求?1????與?2????的最長公共子序列的長度（子序列可以不連續(xù)）。

輸入描述

第一行為字符串?1??，僅由小寫字母組成，長度不超過100；

第一行為字符串?2???，僅由小寫字母組成，長度不超過100。

輸出描述

輸出一個整數(shù)，表示最長公共子序列的長度。

#include<bits/stdc++.h>
using namespace std;
int main(){
    string a,b;
    cin>>a>>b;
    int dp[102][102]={0};
    for(int i=1;i<=a.length();i++){
        for (int j = 1; j <= b.length(); j++){
            if(a[i-1]==b[j-1]){
                dp[i][j]=dp[i-1][j-1]+1;
            }else{
                dp[i][j]=max(dp[i][j-1],dp[i-1][j]);
            }
        }
    }
    cout<<dp[a.length()][b.length()];
    return 0;
}

最長回文子串

最長回文子串

題目描述

現(xiàn)有一個字符串?，求?的最長回文子串的長度。

輸入描述

一個字符串?????，僅由小寫字母組成，長度不超過100。

輸出描述

輸出一個整數(shù)，表示最長回文子串的長度。

//中點(diǎn)擴(kuò)散算法
#include<bits/stdc++.h>
using namespace std;
const int N=1e3+10;
int dp[N][N];
int main()
{
    string str;
    getline(cin,str);
    int res=0;
    for(int i=0;i<str.length();i++)
    {
        int l=i-1,r=i+1;//判斷奇數(shù)長度回文串
        while(l>=0&&r<str.length()&&str[l]==str[r]) l--,r++;
        res=max(res,r-l-1);
        l=i,r=i+1;//判斷偶數(shù)長度回文串
        while(l>=0&&r<str.length()&&str[l]==str[r]) l--,r++;
        res=max(res,r-l-1);
    }
    cout<<res<<endl;
    return 0;
}

背包問題

01背包問題

題目描述

有?件物品，每件物品的重量為??，價值為??。現(xiàn)在需要選出若干件物品放入一個容量為?的背包中（每件物品至多選一次），使得在選入背包的物品重量之和不超過容量?的前提下，讓背包中物品的價值之和最大，求最大價值。

輸入描述

第一行兩個整數(shù)??、??（1≤?≤100,1≤?≤103?），分別表示物品數(shù)量、背包容量；

第二行為用空格隔開的??個整數(shù)???（1≤??≤10?），表示物品重量；

第三行為用空格隔開的??個整數(shù)???（1≤??≤10?），表示物品價值。

輸出描述

輸出一個整數(shù)，表示最大價值。

#include<bits/stdc++.h>
using namespace std ;
int ti[1005] , pri[1005] ;
int f[1005][1005] ;
int main()
{
	int t , m ;
	cin >> m>> t ;
    for(int i = 1 ; i <= m ; ++i){
        cin >> ti[i];
    }
    for(int i = 1 ; i <= m ; ++i){
        cin >> pri[i];
    }
	for(int i = 1 ; i <= m ; ++i)
	{
        for(int j = 1 ; j <= t ; ++j)
		{
			f[i][j] = f[i - 1][j] ;
            if(j >= ti[i]) 
				f[i][j] = max(f[i][j], f[i - 1][j - ti[i]] + pri[i]) ;
        }
    }
    cout << f[m][t] ;
	return 0 ;
}

完全背包問題

題目描述

有??種物品，每種物品的重量為???，價值為???。現(xiàn)在需要選出若干件物品放入一個容量為??的背包中（每種物品可以選任意次），使得在選入背包的物品重量之和不超過容量???的前提下，讓背包中物品的價值之和最大，求最大價值。

輸入描述

第一行兩個整數(shù)??、??（1≤?≤100,1≤?≤103?），分別表示物品數(shù)量、背包容量；

第二行為用空格隔開的??個整數(shù)???（1≤??≤100?），表示物品重量；

第三行為用空格隔開的??個整數(shù)???（1≤??≤100?），表示物品價值。

輸出描述

輸出一個整數(shù)，表示最大價值。

#include<bits/stdc++.h>
using namespace std;
int a[1002]={0},b[1002]={0};
int f[1002]={0};
int main(){
    int n,v;
    cin>>n>>v;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++) cin>>b[i];
    for(int i=1;i<=n;i++){
        for(int j=a[i];j<=v;j++){
			f[j] = max(f[j], f[j - a[i]] +b[i]);
        }
    }
    cout << f[v];
    return 0;
}

01背包問題的方案數(shù)

題目描述

有??件物品，每件物品的重量為???。現(xiàn)在需要選出若干件物品放入一個容量為??的背包中（每件物品至多選一次），使得選入背包的物品重量之和恰好等于容量?????。求滿足條件的方案數(shù)。

輸入描述

第一行兩個整數(shù)??、??（1≤?≤100,1≤?≤103?），分別表示物品數(shù)量、背包容量；

第二行為用空格隔開的??個整數(shù)???（1≤??≤10?），表示物品重量。

輸出描述

輸出一個整數(shù)，表示方案數(shù)。由于結(jié)果可能很大，因此將結(jié)果對10007取模后輸出。

#include<bits/stdc++.h>
using namespace std;
int main(){
	int N,M;
	cin>>N>>M;
	int a[1005],dp[10050];
	for(int i=1;i<=N;i++){
		cin>>a[i];
	}
	dp[0]=1;
	for(int i=1;i<=N;i++){
		for(int j=M;j>=a[i];j--){
			dp[j]=(dp[j]+dp[j-a[i]])%10007;
		}
	}
	cout<<dp[M];
	return 0;
}

總結(jié)

最小消耗能量

題目描述

現(xiàn)有?個從左至右擺放著的高臺（編號為從1到n），每個高臺有各自的高度??。假設(shè)闖關(guān)者當(dāng)前處于第?個高臺，那么可以選擇跳到第?+1或第?+2個高臺（闖關(guān)者能夠跳任意高度）。如果從第?個高臺跳到第?個高臺，那么將會消耗闖關(guān)者|?????|點(diǎn)能量。問從第1個高臺出發(fā)、到達(dá)第?個高臺的過程中需要消耗的最小能量。

輸入描述

第一行一個整數(shù)?（1≤?≤104），表示高臺個數(shù)。

第二行為用空格隔開的?個整數(shù)??（1≤??≤100），表示各高臺的高度。

輸出描述

一個整數(shù)，表示需要消耗的最小能量。

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin>>n;
    int a[10002];
    int dp[10002];
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    for(int i=2;i<=n;i++){
        dp[0]=dp[1]=0;
        dp[i]=dp[i-1]+abs(a[i]-a[i-1]);
        dp[i]=min(dp[i],dp[i-2]+abs(a[i]-a[i-2]));
    }
    cout<<dp[n];
    return 0;

}

矩陣最大權(quán)值

題目描述

現(xiàn)有一個????大小的矩陣，矩陣中的每個元素表示該位置的權(quán)值?，F(xiàn)需要從矩陣左上角出發(fā)到達(dá)右下角，每次移動只能向右或者向下移動一格。求最后到達(dá)右下角時路徑上所有位置的權(quán)值之和的最大值。

輸入描述

第一行兩個整數(shù)?????、?????（1≤?≤100,1≤?≤100????），分別表示矩陣的行數(shù)和列數(shù)；

接下來????行，每行????個整數(shù)（?100≤??整數(shù)≤100???），表示矩陣每個位置的權(quán)值。

輸出描述

一個整數(shù)，表示權(quán)值之和的最大值。

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n,m;
    cin>>n>>m;
    int a[101][101];
    int dp[101][101]={0};
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>a[i][j];
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            dp[1][1]=a[1][1];
            if(i==1&&j!=1){
                dp[i][j]=dp[i][j-1]+a[i][j];
            }
            if(i!=1&&j==1){
                dp[i][j]=dp[i-1][j]+a[i][j];
            }
            if(i!=1&&j!=1){
                dp[i][j]=a[i][j]+max(dp[i-1][j],dp[i][j-1]);
            }
        }
    }
    cout<<dp[n][m];
    return 0;
}

?最小涂色成本

題目描述

現(xiàn)有????張不同大小的白紙排成一排，每張白紙可以涂成紅、黃、藍(lán)三種顏色之一，但不能有連續(xù)兩張白紙涂成相同的顏色。假設(shè)給第????張白紙涂紅色需要消耗的成本為?????，涂黃色需要消耗的成本為????，涂藍(lán)色需要消耗的成本為????，求把?????張白紙全部涂色需要的最小成本。

輸入描述

第一行一個整數(shù)????????????（1≤?≤104???????），表示白紙張數(shù)；

接下來?行，每行三個整數(shù)，表示第?張白紙分別涂紅、黃、藍(lán)三種顏色需要消耗的成本??、??、??（1≤??≤100,1≤??≤100,1≤??≤100?）。

輸出描述

一個整數(shù)，表示最小成本。文章來源地址http://www.zghlxwxcb.cn/news/detail-857851.html

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin>>n;
    int a[10001][4];
    int dp[10001][4];
    for(int i=1;i<=n;i++){
        for(int j=1;j<=3;j++){
            cin>>a[i][j];
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=3;j++){
            if(i==1) dp[i][j]=a[i][j];
            else{
                if(j==1) dp[i][1]=a[i][j]+min(dp[i-1][2],dp[i-1][3]);
                if(j==2) dp[i][2]=a[i][j]+min(dp[i-1][1],dp[i-1][3]);
                if(j==3) dp[i][3]=a[i][j]+min(dp[i-1][1],dp[i-1][2]);
            }  
        }
    }  
    cout<<min(min(dp[n][1], dp[n][2]), dp[n][3]);
    return 0;  

}

到了這里，關(guān)于晴問算法動態(tài)規(guī)劃（簡單）的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！

本文來自互聯(lián)網(wǎng)用戶投稿，該文觀點(diǎn)僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務(wù)，不擁有所有權(quán)，不承擔(dān)相關(guān)法律責(zé)任。如若轉(zhuǎn)載，請注明出處：如若內(nèi)容造成侵權(quán)/違法違規(guī)/事實(shí)不符，請點(diǎn)擊違法舉報進(jìn)行投訴反饋，一經(jīng)查實(shí)，立即刪除！

分享到：

領(lǐng)支付寶紅包贊助服務(wù)器費(fèi)用

算法沉淀 —— 動態(tài)規(guī)劃篇（簡單多狀態(tài)dp問題上）
幾乎所有的動態(tài)規(guī)劃問題大致可分為以下5個步驟，后續(xù)所有問題分析都將基于此 1.、狀態(tài)表示：通常狀態(tài)表示分為以下兩種，其中更是第一種為主。以i為結(jié)尾，dp[i] 表示什么，通常為代求問題（具體依題目而定）以i為開始，dp[i]表示什么，通常為代求問題（具體依題目而
2024年04月11日
瀏覽(31)
【動態(tài)規(guī)劃專欄】--簡單-- 動態(tài)規(guī)劃經(jīng)典題型
目錄動態(tài)規(guī)劃動態(tài)規(guī)劃思維（基礎(chǔ)）狀態(tài)表示（最重要）狀態(tài)轉(zhuǎn)移方程（最難）初始化（細(xì)節(jié)）填表順序（細(xì)節(jié)）返回值（結(jié)果）解碼方法?? 【題目解析】? ?【算法原理】 C++ 算法代碼復(fù)雜度分析【空間優(yōu)化 - 滾動數(shù)組】 C++ 算法代碼復(fù)雜度分析【DP邊界、初始化
2024年02月08日
瀏覽(30)
力扣：動態(tài)規(guī)劃簡單題集解
一般，只要解決問題的階段、狀態(tài)和狀態(tài)轉(zhuǎn)移決策確定了，就可以寫出狀態(tài)轉(zhuǎn)移方程（包括邊界條件）。根據(jù)動態(tài)規(guī)劃的三大基本要素可以設(shè)計解題步驟如下：狀態(tài)定義：每個狀態(tài)的決策，存放每個狀態(tài)的變量，狀態(tài)轉(zhuǎn)移方程：當(dāng)前狀態(tài)與上一個狀態(tài)之間的關(guān)系初始狀態(tài)
2024年02月08日
瀏覽(11)
動態(tài)規(guī)劃之簡單多狀態(tài)
1.題目鏈接：按摩師 2.題目描述：一個有名的按摩師會收到源源不斷的預(yù)約請求，每個預(yù)約都可以選擇接或不接。在每次預(yù)約服務(wù)之間要有休息時間，因此她不能接受相鄰的預(yù)約。給定一個預(yù)約請求序列，替按摩師找到最優(yōu)的預(yù)約集合（總預(yù)約時間最長），返回總的分鐘數(shù)。
2024年02月09日
瀏覽(20)
【動態(tài)規(guī)劃】簡單多狀態(tài)
題目鏈接狀態(tài)表示 dp[i] 表示到i位置的時候預(yù)約的最大時長。但是這個題目我們可以選擇接或不接。因此可以繼續(xù)劃分為兩個子狀態(tài)： f[i] 表示：到i位置時接受的最大時長 g[i] 表示：到i位置時不接受的最大時長狀態(tài)轉(zhuǎn)移方程初始化因為這個題目比較簡單，所以不需要使用
2024年02月15日
瀏覽(23)
1.20 動態(tài)規(guī)劃（簡單）
目錄動態(tài)規(guī)劃解題思路動態(tài)規(guī)劃的做題步驟 1. 爬樓梯 2.楊輝三角 3.買賣股票的最佳時機(jī) 假設(shè)你正在爬樓梯。需要? n ?階你才能到達(dá)樓頂。每次你可以爬? 1 ?或? 2 ?個臺階。你有多少種不同的方法可以爬到樓頂呢？示例 1：示例 2：提示： 1 = n = 45 ?分析：從分析來看，
2024年01月24日
瀏覽(17)
【算法】動態(tài)規(guī)劃 ⑧ ( 動態(tài)規(guī)劃特點(diǎn) )
求解類型 : 動態(tài)規(guī)劃必須是求最值 , 可行性 , 方案數(shù) , 三者之一 , 如果求其它內(nèi)容 , 則不能使用動態(tài)規(guī)劃算法 ; 求最值 : 最大值 , 最小值等 ; 大規(guī)模問題的結(jié)果由小規(guī)模問題的計算結(jié)果取最大值大規(guī)模問題的結(jié)果由小規(guī)模問題的計算結(jié)果取最小值可行性 : 是否可行
2023年04月08日
瀏覽(22)
c++--簡單多狀態(tài)動態(tài)規(guī)劃問題
PS:以下代碼均為C++實(shí)現(xiàn) 1.按摩師? 力扣一個有名的按摩師會收到源源不斷的預(yù)約請求，每個預(yù)約都可以選擇接或不接。在每次預(yù)約服務(wù)之間要有休息時間，因此她不能接受相鄰的預(yù)約。給定一個預(yù)約請求序列，替按摩師找到最優(yōu)的預(yù)約集合（總預(yù)約時間最長），返回總的分鐘
2024年02月14日
瀏覽(32)
「動態(tài)規(guī)劃」簡單多狀態(tài)dp問題
以經(jīng)典問題“打家劫舍”來解釋簡單多狀態(tài)dp問題和解決方法題目鏈接：打家劫舍I 這種問題就是在某一個位置有多個狀態(tài)可以選擇，選擇不同的狀態(tài) 會影響最終結(jié)果在這道題中就是小偷在每一個房屋，可以選擇偷或不偷，每一次選擇都會影響最終偷竊金額狀態(tài)表示因為
2024年03月15日
瀏覽(29)
60題學(xué)會動態(tài)規(guī)劃系列：動態(tài)規(guī)劃算法第三講
簡單多狀態(tài)問題文章目錄一.按摩師二.打家劫舍系列三.刪除并獲得點(diǎn)數(shù) 四.粉刷房子力扣鏈接：力扣一個有名的按摩師會收到源源不斷的預(yù)約請求，每個預(yù)約都可以選擇接或不接。在每次預(yù)約服務(wù)之間要有休息時間，因此她不能接受相鄰的預(yù)約。給定一個預(yù)約請求序列，
2024年02月08日
瀏覽(24)