首先用最經典的一道題來引入動態規劃
動態規劃（dynamic programming）
請看下面這個題
一個十分漂亮的數字三角形；求哪條路徑能使得各個數字的和最大；
如果我們只是單純的貪心，即每次選擇最大值走，
那么結果就是7+8+1+7+5=28；
但是，7+3+8+7+5這條路徑等于三十30；
顯然，不能使用貪心的思想；
這時候，就需要使用動態規劃的思想；
主要思想：
將問題可以看為多個相同的小問題，尋找最優子結構，利用區域最優解推匯出整體最優解；
這個類似于完全二叉樹的東西，每一個父節點都有兩個子節點，那么父節點的路徑只有他的兩個子結構，所以此時我們需要找出哪一個子節點大，
例如：
2
4 5
這個節點；
顯然5>4，那么我們遞推的時候就會采用5而不是4；
假設第i行j列的節點為dp[i][j]；
那么他的遞推公式就是dp[i][j]+=max{dp[i-1][j],dp[i-1][j];
選擇大的位元組；一層一層累加上去，那么dp[0][0]便是最大路徑的值
原始碼如下：
#include<iostream>
#include<cmath>
#include<cstdio>
#include<algorithm>
using namespace std;
int num[1001][1001];
int main()
{
int n;
cin >> n;
for (int i = 0; i < n; i++)
{
for (int j = 0; j <= i; j++)
{
cin >> num[i][j];
}
}
for (int i = n-1; i >=0; i--)
{
for (int j = 0; j <= i; j++)
{
num[i][j] = (num[i + 1][j] > num[i + 1][j + 1] ? num[i + 1][j] : num[i + 1][j + 1]) + num[i][j];
}
}
cout << num[0][0];
return 0;
}
所以說，動態規劃大致就分為以下步驟：
- 拆分問題；
- 找遞推公式（狀態轉移方程）；
- 確定邊界；
再看一道：
leetcode 70；
問題問，有幾種方法；題目已知，可以跳一個，也可以跳兩個，假設跳到第i個的時候，絕對是從第i-1或者i-2個樓梯來的，那么他的狀態轉移方程就出來了
dp[i]=dp[i-1]+dp[i-2]；
然后確定邊界，首先第0個絕對是0種方法，第1個也只有一種，第二個有2種，；
即dp[1]=1,dp[2]=2；
原始碼如下：
int climbStairs(int n)
{
int dp[50]={1,2};
for(int i=2;i<n;i++)
{
dp[i]=dp[i-1]+dp[i-2];
}
return dp[n-1];
}
最后，再來一道leetcode與上題相近的中等題
這個時候，我們根據上個題，可以很容易想來；
第i行j列的方法，就是第i-1行j列+第i行j-1列之和；
所以他的遞推公式就是:dp[i][j]=dp[i-1][j]+dp[i][j-1];
此時地圖的最上一行和最左邊的一行；他們都只能由一種走來；
最上面的一行每一個格子只能由他的左邊走來，最左邊的格子只能由他上面的格子走來；
所以，這個題的初始化就是：
int dp[m][n];
for(int i=0;i<m;i++)
{
dp[i][0]=1;
}
for(int i=0;i<n;i++)
{
dp[0][i]=1;
}
現在知道狀態轉移方程和邊界；
直接上原始碼：
int uniquePaths(int m, int n){
int dp[m][n];
for(int i=0;i<m;i++)
{
dp[i][0]=1;
}
for(int i=0;i<n;i++)
{
dp[0][i]=1;
}
for(int i=1;i<m;i++)
{
for(int j=1;j<n;j++)
{
dp[i][j]=dp[i-1][j]+dp[i][j-1];
}
}
return dp[m-1][n-1];
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qianduan/264506.html
標籤：其他
上一篇：js型別轉換
下一篇：JavaScript中的跨域問題