データ構造とアルゴリズム(C++)–動的計画(Dynamic Programming)

ダイナミックプランニング(Dynamic Programming)
動的計画の好文を理解する:https://www.sohu.com/a/153858619_466939
1、基礎
**定義:**再帰アルゴリズムでは、しばしば計算が繰り返され、プログラムの効率が低下します.動的計画はこの問題を解決する方法である.
動的計画の構成要素:

最適サブ構造:分解問題

境界:再帰的終了条件

状態遷移方程式:再帰的方程式

動的計画の解題手順:

問題を分解し,状態遷移方程式

を得た.

暴力的に捜索し、冗長性を見つけ、通常は純再帰

である.

は、計算された結果を格納し、通常は配列および辞書

を用いる.

プログラミングでは、通常、ボトムアップ思想(プッシュ)

を採用する.
2、階段の問題
**テーマ:**10段の階段があり、下から上へ行くと、一歩ごとに1段または2段の階段しか上がらない.全部で何種類の歩き方があるかをプログラムで求めるように要求した.
再帰解法:

int solve(int n)
{
	if(n < 1)
		return 0;
	if(n == 1)
		return 1;
	if(n == 2)
		return 2;
	
	return solve(n-1)+solve(n-2);
}

メモの解法:

int solve(int n，HashMapmap)
{
	if(n < 1)
		return 0;
	if(n == 1)
		return 1;
	if(n == 2)
		return 2;
	
	if(map.contains(n))
		return map.get(n);
	else
	{
		int value = solve(n-1)+solve(n-2);
		map.put(n, value);
		return value;
	}
}

動的計画解法:

int solve(int n，HashMapmap)
{
	if(n < 1)
		return 0;
	if(n == 1)
		return 1;
	if(n == 2)
		return 2;
	
	int a = 1;
	int b = 2:
	int temp = 0;
	
	for(int i=3; i<=n; i++)
	{
		temp = a + b;
		a = b;
		b = temp;
	}

	return temp;
}

問題は1回で最大k段の階段を歩けるように変更しました
考え方:実は同じで、境界と再帰式をkに拡張すればいいです.

//     ,       k    ，     ，  k  2^(k-1)   
num[0] = 1
for(int i=1; i =< k; ++i)
	num[i] = power(2, i-1);

//   
for(int j = k+1; j

3、家庭強盗問題
**テーマ:**商店を盗んで、连続して2家を盗むことができなくて、盗む総额を求めます最大
メモの解法:

vector save;    
int solve(vector& nums, int n)
{
	if(n < 0)
        return 0;
    if(save[n] >= 0)
        return save[n];
    
    save[n] = max(solve(nums, n-2)+nums[n], solve(nums, n-1));
           
    return save[n];
}
int rob(vector& nums) {
    int len = nums.size();
    for(int i=0; i

動的計画解法:

int rob(vector& nums) {
	int n = nums.size(); 
    if(n == 0)
        return 0;
    if(n == 1)
        return nums[0];
 
    vector save(n, -1);
    save[0] = nums[0];
    save[1] = max(nums[0], nums[1]);
    
    for(int i=2; i

4、01リュックの問題
テーマ:n種類の物品と1つの容量がCのリュックサックを与えて、物品iの重量はwiで、その価値はviで、どのようにリュックサックの中に入る物品を選んで、リュックサックの中に入る物品の総価値を最大にするべきですか?

//    0   ，    ，  0
int v[N]={0,8,10,6,3,7,2};
int w[N]={0,4,6,2,2,5,1};
int n=6,c=12;

int solve()
{
	//           m[i][0]，m[0][j]    0，         0
	int m[n+1][c+1] = {0};
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=c;j++)
        {
            if(j>=w[i])
                m[i][j]=max(m[i-1][j],m[i-1][j-w[i]]+v[i]);  
            else
                m[i][j]=m[i-1][j];
        }
    }
    return m[n][c]

2 x(c+1)または1 x(c+1)サイズの配列のみで空間をさらに圧縮できます.

# 2x(c+1)  
int m[2][c+1] = {0};
m[i%2][j]=max(m[(i-1)%2][j],m[(i-1)%2][j-w[i]]+v[i]);  

# 1x(c+1)     
int m[c+1] = {0};
m[j]=max(m[j],m[j-w[i]]+v[i]);  

5、コインのお釣り
标题:コインの種類値リストcoin_List、小銭change元を探して、最低何個のコインが必要ですか?
再帰解法:

def find_coins(coin_list, change):
    min_coins = change
    if change in coin_list:
        return 1
    else:
        for i in [c for c in coin_list if c <= change]:
            num_coins = 1 + find_coins(coin_list, change-i)
            if num_coins < min_coins:
                min_coins = num_coins
    return min_coins

print(recDC([1,5,10,25], 63)

メモの解法:

# save_list               ，    =        +1，    =0
def find_coins(coin_list, change, save_list):
    min_coins = change
    if change in coin_list:
        return 1
    elif save_list[change] > 0:
        return save_list[change]
    else:
        for i in [c for c in coin_list if c <= change]:
            num_coins = 1 + find_coins(coin_list, change-i, save_list)
            if num_coins < min_coins:
                min_coins = num_coins
                save_list[change] = min_coins
    return min_coins

print(recDC([1,5,10,25], 63, [0]*64))

動的計画解法:

#   
def find_coins(coins_list, change, min_coins_list):
    for num in range(change+1):
        num_coins = num
        for j in [c for c in coins_list if c <= num]:
            if min_coins_list[num-j] + 1 <= num_coins:
                num_coins = min_coins_list[num-j]+1
                min_coins_list[num] = num_coins
    return min_coins_list[change]


print(find_coins([1, 5, 10, 25], 63, [0]*64))

GOOD LUCK!