动态规划用于解决重叠子问题(overlap sub-problem)，已经计算过的不再重复计算，而是从内存中重新调出来使用。
LeetCode 按摩师（同打家劫舍系列）
给定预约时长，找到最优的预约集合(时长最长)，且不能接收相邻的预约
输入： [2,1,4,5,3,1,1,3]
输出： 12
解释： 选择 1 号预约、 3 号预约、 5 号预约和 8 号预约，总时长 = 2 + 4 + 3 + 3 = 12。
1
2
3
4
5
6
7
8
9
10
11
12
13
| int massage(vector<int>& nums) {
int dp[10000];
if(nums.size() == 0 )
return 0;
else if(nums.size() == 1)
return nums[0];
dp[0] = nums[0];
dp[1] = max(nums[0],nums[1]);
for(int i = 2; i < nums.size(); i++){
dp[i] = max(dp[i-1],dp[i-2]+nums[i]);
}
return dp[nums.size()-1];
}
|
LeetCode 编辑距离
e.g.
|
‘’ |
r |
o |
s |
| ‘’ |
0 |
1 |
2 |
3 |
| h |
1 |
1 |
2 |
3 |
| o |
2 |
2 |
1 |
2 |
| r |
3 |
2 |
2 |
2 |
| s |
4 |
3 |
3 |
2 |
| e |
5 |
4 |
4 |
3 |
dp[i-1][j-1]是替换操作，dp[i-1][j]是删除操作，dp[i][j-1]是插入操作。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| int minDistance(string word1, string word2) {
int n = word1.size();
int m = word2.size();
int dp[n + 1][m + 1];
memset(dp,0,sizeof(dp));
for(int i = 1; i <= n; i++)
dp[i][0] = dp[i - 1][0] + 1;
for(int j = 1; j <= m; j++)
dp[0][j] = dp[0][j - 1] + 1;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
if(word1[i-1] == word2[j-1]){
dp[i][j] = dp[i - 1][j - 1];
}
else{
dp[i][j] = min(min(dp[i-1][j-1],dp[i][j-1]),dp[i-1][j])+ 1;
}
}
}
return dp[n][m];
}
|
