動态規劃：數字和為sum的方法數

題目描述

給定一個有n個正整數的數組A和一個整數sum,求選擇數組A中部分數字和為sum的方案數。

當兩種選取方案有一個數字的下标不一樣,我們就認為是不同的組成方案。

輸入描述:

輸入為兩行:
 第一行為兩個正整數n(1 ≤ n ≤ 1000)，sum(1 ≤ sum ≤ 1000)
 第二行為n個正整數A[i](32位整數)，以空格隔開。      

輸出描述:

輸入

5 15 
5 5 10 2 3      

輸出

4      

#include<iostream>
#include<vector>
using namespace std;
int main()
{
	int n, sum;
	cin >> n >> sum;
	vector<long>vec(sum + 1, 0), input(n + 1, 0);
	vec[0] = 1;這一步的目的是如果目前數字中的元素剛好等于要求的，就是多一種方法
			   //如果不指派為1，還是為0就沒辦法加一種方法
	vector<vector<long> >result(n + 1, vec);
	for (int i = 1; i <= n; i++)
	{
		cin >> input[i];
	}
	//程式多加一行的目的是，例如：result[1][5]=result[0][5]+result[0][5-input[1]](即result[0][0])
	//多加一行友善整體運算不需分類計算
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= sum; j++)
		{
			if (j - input[i] >= 0)
			{
				//如果列所在數字減去該行數大于等于0，該格子内容為該列上一行數字與上一行差
				// 值所在格子數量和。什麼意思呢？例如(10,3)，若想要用3之前的數列得到10，除了
				// 它上一行(即2)本身就能得到2個10外，隻要之前的數字是7,7+3依然可以得到10。因
				// 此去看上一行中列數為7的格子數值，為2，即它上一個數有2中組合得到7,7+3=10。
				// 那該行數值即為2+2=4。
				result[i][j] = result[i - 1][j] + result[i - 1][j - input[i]];
			}
			else
			{//果列所在數字減去該行數小于0，那麼該格子繼承本列上一行的數字。
				result[i][j] = result[i - 1][j];
			}
		}
	}
	cout << result[n][sum] << endl;
	return 0;
}
           

　　

如果是使用上面的用例圖解圖上圖所示，

 然後說一下做法： 1.由于每個數總能把0填上，且0不可填上初0外其餘數，是以數組第一行全填0，第一列全填1；  2.從第二行第二列開始周遊數組。如果列所在數字減去該行數小于0，那麼該格子繼承本列上一行的數字。例如圖中(2,10)對應格子。由于讓10得到2，那必須由-8+5得到，但是該題無法得到比0小的數，是以由10之前的數得到2的最多可能與他之前的數（即5）是一樣的； 3.如果列所在數字減去該行數大于等于0，該格子内容為該列上一行數字與上一行內插補點所在格子數量和。什麼意思呢？例如(10,3)，若想要用3之前的數列得到10，除了它上一行(即2)本身就能得到2個10外，隻要之前的數字是7,7+3依然可以得到10。因 此去看上一行中列數為7的格子數值，為2，即它上一個數有2中組合得到7,7+3=10。  那該行數值即為2+2=4。

轉載于:https://www.cnblogs.com/wuyepeng/p/9672154.html