【动态规划】Part1

1. 硬币找零

题目描述：假设有几种硬币，如1、3、5，并且数量无限。请找出能够组成某个数目的找零所使用最少的硬币数。

分析： dp [0] = 0
dp [1] = 1 + dp [1-1]
dp [2] = 1 + dp [2-1]
dp [3] = min (dp [3 - 1] + 1, dp [3 - 3] + 1)

 1 #include<iostream>
 2 #include<algorithm>
 3 #define INF 32767
 4 using namespace std;
 5 
 6 int dp[100];
 7 int coin[3] = { 1, 2, 3 };
 8 
 9 int main()
10 {
11     int sum;
12     cin >> sum;
13     dp[0] = 0;
14     for (int i = 1; i <= 100; ++i)
15         dp[i] = INF;
16     for (int i = 1; i <= sum; ++i)
17         for (int j = 0; j <= 2; ++j)
18             if (coin[j] <= i)
19                 dp[i] = min(dp[i], dp[i - coin[j]] + 1);
20     cout << dp[sum] << endl;
21     return 0;
22 }

2. 最长递增子序列

• 题目描述：最长递增子序列（Longest Increasing Subsequence）是指找到一个给定序列的最长子序列的长度，使得子序列中的所有元素单调递增。

给定一个序列，求解它的最长递增子序列的长度。比如： arr[] = {3,1,4,1,5,9,2,6,5} 的最长递增子序列长度为4。即为：1,4,5,9

 1 #include<iostream>
 2 #include<algorithm>
 3 using namespace std;
 4 
 5 int arr[9] = { 3, 1, 4, 1, 5, 9, 2, 6, 5 };
 6 int dp[9];
 7 
 8 int main()
 9 {
10     for (int i = 0; i < 9; ++i)
11         dp[i] = 1;
12     for (int i = 1; i < 9; ++i)
13         for (int j = 0; j < i; ++j)
14             if (arr[i] > arr[j])
15                 dp[i] = max(dp[i], dp[j] + 1);
16     int mi = 0;
17     for (int i = 0; i < 6; ++i)
18         mi = max(mi, dp[i]);
19     cout << mi << endl;
20     return 0;
21 }

3. 数字三角形

Problem description

7

3   8

8   1   0

2   7   4   4

4   5   2   6   5



(Figure 1)

Figure 1 shows a number triangle. Write a program that calculates the highest sum of numbers passed on a route that starts at the top and ends somewhere on the base. Each step can go either diagonally down to the left or diagonally down to the right.

Input

Your program is to read from standard input. The first line contains one integer T, the number of test cases, for each test case: the first line contain a integer N: the number of rows in the triangle. The following N lines describe the data of the triangle. The number of rows in the triangle is > 1 but <= 100. The numbers in the triangle, all integers, are between 0 and 99.

Output

Your program is to write to standard output. The highest sum is written as an integer for each test case one line.

Sample Input

Sample Output

Problem Source

IOI 1994

代码：

 1 #include<iostream>
 2 #include<algorithm>
 3 using namespace std;
 4 
 5 int dp[100][100];
 6 int arr[100][100];
 7 
 8 int main()
 9 {
10     int N;
11     cin >> N;
12     if (N == 1)
13         cout << N;
14     for (int i = 0; i < N; ++i)
15         for (int j = 0; j <= i; ++j)
16             cin >> arr[i][j];
17     for (int i = 0; i < N; ++i)
18         dp[N - 1][i] = arr[N - 1][i];
19     for (int i = N - 2; i >= 0; --i)
20         for (int j = 0; j <= i; ++j)
21             dp[i][j] = max(arr[i][j] + dp[i + 1][j], arr[i][j] + dp[i + 1][j + 1]);
22     cout << dp[0][0] << endl;
23     return 0;
24 }

4. 最大最大连续子序列和/积

• 求取数组中最大连续子序列和，例如给定数组为A={1， 3， -2， 4， -5}，则最大连续子序列和为6，即1+3+（-2）+ 4 = 6。

• 求取数组中最大连续子序列积。

参考资料

• 常见动态规划问题分析与求解
• 关于序列的面试题2------------最大连续子序列和以及积