小白勿噴~~（點亮你的“小紅花”）
下面是我對動態規劃的一些認識：
動態規劃的主要解決的就是一個大問題的最優解，然后這個大問題的最優解可以轉化為很多個子問題的最優解，如果無法轉化，則不能通過此演算法來解決，
我們在將大問題轉化為小問題的時候，很容易就會想到用遞回的方式解決，但資料過大，重復的遞回呼叫會讓我們的時間復雜度變得非常的大，
下面我會通過分析遞回呼叫的方式和動歸呼叫的方式進行決議，
我們就以數字三角形為例子來進行分析，
遞回版本：
#include<iostream>
#include<algorithm>
using namespace std;
#define max1 101
int dp[max1][max1];//定義一個二維陣列來保存數字三角形
int n;//表示數字三角形的行數
int maxsum[max1][max1];//用來保存第i行第j列數字到底邊的最大和
int maxs(int i,int j)//求第i行第j列的數字到底邊的最大距離的函式
{
if(i==n)
maxsum[i][j]=dp[i][j]; //如果計算的數字在最后一行，就直接回傳當前值
else
{
int a=maxs(i+1,j);//當前數字左下的數字,遞回呼叫計算，值為-1就直接從函式中回傳值，如果不是就繼續往下算，下同
int b=maxs(i+1,j+1);//當前數字右下數字，同上
maxsum[i][j]=max(a,b)+dp[i][j]; //左下數字和右下數字比較，大的那個加上當前數字
}
return maxsum[i][j];
}
int main()
{
int i,j;
cin>>n;
for(int i=1;i<=n;i++)
for(int j=1;j<=i;j++)
{
cin>>dp[i][j];
}
cout<<maxs(1,1)<<endl;
}
遞回演算法的唯一優點就是寫法簡單，容易理解，但資料一多，重復計算的數字也多，所以容易超時，下面我們來看動態規劃計算的版本，
動歸方式：
#include<iostream>
#include<algorithm>
using namespace std;
#define max1 101
int dp[max1][max1];//定義一個二維陣列來保存數字三角形
int n;//表示數字三角形的行數
int maxsum[max1][max1];//用來保存第i行第j列數字到底邊的最大和
int maxs(int i,int j)//求第i行第j列的數字到底邊的最大距離的函式
{
if(maxsum[i][j]!=-1)//如果當前值(狀態)不為-1，就直接回傳當前值，不用再進行重復計算，降低了時間復雜度
{
return maxsum[i][j];
}
if(i==n)
maxsum[i][j]=dp[i][j];
if(maxsum[i][j]==-1)
{
int a=maxs(i+1,j);//當前數字左下的數字,遞回呼叫計算，值為-1就直接從函式中回傳值，如果不是就繼續往下算，下同
int b=maxs(i+1,j+1);//當前數字右下數字，同上
maxsum[i][j]=max(a,b)+dp[i][j]; //左下數字和右下數字比較，大的那個加上當前數字
}
return maxsum[i][j];
}
int main()
{
int i,j;
cin>>n;
for(int i=1;i<=n;i++)
for(int j=1;j<=i;j++)
{
cin>>dp[i][j];
maxsum[i][j]=-1;//為了避免重復計算，我們將第i行第j列的數字到底邊距離初始化為-1
}
cout<<maxs(1,1)<<endl;
}
動歸方式的計算，就是初始化了每一個數到底邊的最大和狀態為-1，當算出來了值就不為-1了，下次要呼叫就直接用其算出來的值，而不用像遞回一樣，再次重復計算，降低了時間復雜度，
當然這個數字三角形還有一種遞推的演算法，就是從底層數字往上計算，在計算到每一層的時候，挑選最大的那個數字往上加，直到加到第i行第j列的數字為止，這種演算法也可選，我就不寫出來了，
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/274100.html
標籤：其他
上一篇：從零開始學python | 什么是Python JSON？
下一篇：初識C語言