动态规划的概念和策略
概念
每次决策都依赖于当前状态，又随即引起状态的转移。一个决策的序列就是在变化的状态中产生出啊来的，所以，这种这种多阶段最优化决策解决问题的过程称为动态规划。
动态规划的基本思想和策略
将带求解的问题分解为若干个子问题，按顺序求解子问题，前一子问题的姐为后一子问题的求解提供了有用的信息。
能用动态规划求解的问题一般具有三个性质：
- 最优化原理
- 无后效性
- 有重叠子问题
动态规划求解问题的步骤：
- 划分阶段
- 确定状态和状态变量
- 确定决策并写出状态转移方程
- 寻找边界条件
示例
字符串解码
题目要求：
一个包含字母的消息被加密之后变成了一个只包含数字的字符串，但是我们现在知道加密规则：
‘A’->1
‘B’->2
…
‘Z’->26
现在给定一个已经加密的只包含数字的字符串，求出改字符串有多少种被解密的方法。例如，”12”->”AB”,”12”->”L”
思路：
这是一个典型的DP问题，假设定义一个数组，dp[i]为到第i个字符所能组成的所有编码方式的个数，那么对于dp[i+1]来说，肯定至少和dp[i]一样多，如果第i个字符和第i+1个字符能合成一个字符，那么dp[i+1] += dp[i-1]
代码(C++)：
#include <iostream>
#include <string>
#include <vector>
using namespace std;
/**
* 思路：
* 这是一个典型的DP问题，假设定义一个数组，dp[i]为到第i个字符所能组成的
* 所有编码方式的个数，那么对于dp[i+1]来说，肯定至少和dp[i]一样多，如果
* 第i个字符和第i+1个字符能合成一个字符，那么dp[i+1] += dp[i-1]
*/
int Decode_num(string &str) {
vector<int> vec(str.size(), 1);
if (str.size() < 2)
return 1;
if (str[0] == '1' || (str[0] == '2' && str[1] <= '6'))
vec[1] = 2;
int i;
int temp;
for (i = 2; i < str.size(); i++) {
if (str[i] >= '0' && str[i] <= '9')//判断是否合法字符
vec[i] = vec[i - 1];
else
return 0;
temp = str[i - 1] - '0';
temp = temp * 10 + str[i] - '0';
if (str[i - 1] != 0 && temp <= 26)
vec[i] += vec[i - 2];
}
return vec[str.size() - 1];
}
int main() {
string str("1231725");
int ret = Decode_num(str);
cout << ret <<endl;
return 0;
}
代码(Go)：
package main
import "fmt"
/**
思路：
这是一个典型的DP问题，假设定义一个数组，dp[i]为到第i个字符所能组成的
所有编码方式的个数，那么对于dp[i+1]来说，肯定至少和dp[i]一样多，如果
第i个字符和第i+1个字符能合成一个字符，那么dp[i+1] += dp[i-1]
*/
func DecodeNum(str string) int {
var s []int
s = append(s, 1)
if len(str) < 2 {
return 1
}
if str[0] == '1' || (str[0] == '2' && str[1] <= '6') {
s = append(s, 2)
}
i, temp := 0, 0
for i = 2; i < len(str); i++ {
if str[i] >= '0' && str[i] <= '9' {
s = append(s, s[i-1])
} else {
return 0
}
temp = int(str[i-1] - '0')
temp = temp*10 + int(str[i]-'0')
if str[i-1] != '0' && temp <= 26 {
s[i] += s[i-2]
}
}
return s[len(str)-1]
}
func main() {
str := "1231725"
fmt.Println(DecodeNum(str))
}
