初探動態規劃（一）

近來把leetcode上關於動態規劃的題目整理了一下。//抱著重新溫習的想法梳理一遍。

之前一直覺得動態規劃只要找到動態轉移方程就行了，後來發現還是有許多坑。 Orz

p.s. 本文題目選自leetcode P474以及 P494

問題 一

在計算機世界中，我們通常使用最少的資源去獲取最大的利益。

現在，假設你擁有m個0和n個1。同時，這裡有一組由0,1隨機組合組成的序列。

你的任務是用你所擁有的0,1資源去匹配最大可能符合的所有字元串。每一個0,1序列最多只能匹配一次，擁有的0,1數也只能用一次。

注意：

1. 給定0,1的數量不會超過100

2. 給定的序列不會超過600

例1

輸入: Array = {"10", "0001", "111001", "1", "0"}, m = 5, n = 3

解釋:我們可以用擁有的5個『0』和3個『1』分別組成「10」， 「0001」， 「1」， 「0」.

例2

輸入: Array = {"10", "0", "1"}, m = 1, n = 1

輸出: 2

解釋: 儘管我們可以組成「10」， 但是這樣並不能獲得最大數量，一個更好的策略是，組成"0", "1".

解析

此題類似於背包問題。我們可以對該問題稍微做一個變型：將給定的字元串數組，根據其每個字元串中含有0,1的個數，用表示0,1個數的數量去代表他。（這裡並不需要考慮在某一個字元串中0,1的排列順序。）

即把輸入格式從

vector<string>& strs --> vector<pair<int, int>> pairs.

這樣，原問題就轉化為

給定 個0和 個1，現有一系列物品，每個物品需要 個0和 個1，求能夠獲得最大物品的數量。

因此，我們定義一個二維數組 代表當我們有i個0，j個1時，最多能夠獲得多少物品。

則狀態轉移方程： 即我們取在放入當前 所需 個1與 個0前能夠獲得最多的那一組。

參考代碼

問題 二

給定一組非負整數序列 以及一個目標值 . 現在，我們有兩種符號"+", "-".對於每一個整數，你可以選擇對其施展」+「或」-"操作作為它的前綴。

我們需要找出一共有多少種符號賦予的方法，使得這一組非負整數通過這些符號，得出的運算結果等於目標值

注意：

1. 非負整數的長度不會超過20。

2. 非負整數序列的和不會超過1000。

3. 輸出的結果在大小4位元組以內。

例1

輸入: nums is [1, 1, 1, 1, 1], S is 3.

解析

最容易想到的方法是回溯法。但是考慮到最長長度為20，極限情況下會將嘗試 次種可能性。一般leet不給過。於是考慮dp方法解決。

同樣的，將該問題進行適當的轉化：問題其實將原序列（集合）劃分為一組正集合和一組負組合（由被賦予「-"的數組成），因此：

(1)

(2)

兩式相減, 有：

(3)

也就是

(4)

其中，(4) 式右側皆是常量。 因此問題轉化為：

已知集合 ，求所有和等於 的子集的數量。 也就是subset sum問題。

因此，我們定義一個一維數組 ，代表目標值為i時，所有滿足條件的子集數量。

其狀態轉移方程：

參考代碼

有一些比較細節的地方， 在考慮給定數組元素是否可重用上，會導致部分遍歷方式不一樣。 很有意思 ：）