首先讲讲何为动态规划 动态规划: 求解决策问题的最优化原理的数学方法，将多个阶段问题进行逐一分解为单阶段问题，构成一个最优决策子序列，最优决策子序列必须保证为局部最优决策子序列，然后再利用各阶段的关系进行逐一解决。 动态规划问题的求解： 状态转移方程尤为重要，用数学公式描述与阶段相关的状态的演变规律称为状态转移方程如：p(x, y) = min{p(x-1, y)+v(x-1, y), p(x-1, y-1)+h(x, y-1)}, p代表前一阶段，当然这是需要分析各阶段量之间的关系才能得出。 动态规划的特点及使用： 1.待解问题具有无后效性，所谓无后效性是指将待解问题转化为多阶段问题，而每一阶段问题都为原问题的一个子问题，子问题的解决只与当前阶段与以后阶段有关，与以前阶段的各决策无关。 2.待解问题能够实施最优最优策略，无论过去的状态及决策如何，对于当前阶段，以后的决策必须能够构成最优决策子序列。 3.保证足够大的内存空间。
题意: 自然数N的k进制表示相邻两位并不是相邻的数字，例如2位4进制数: 有11、13、20、22、30、31、33，共7个。 输入：N K (N代表位数，K代表进制数) 输出：K好数总个数 例： 输入：2 4 输出：7 这一题就是一个十分典型动态规划的题目，我们首先分析: 当为1位4进制时，可取为0、1、2、3共4个 当为2位4进制时，可取为11、13、20、22、30、31、33共7个 当为3为4进制时，前置为11的三位4进制数可以表示为两位以1为首的4进制数，也就是11、13，同理前置为13的三位4进制数可以表示为以两位以3为首的4进制数，即30、31、33，… 这时我们可以画一个表格来更形象的表示： 还需要注意的是，在位1位时开头可以为0，但是两位及以上时则开头不能为0。 代码如下：
#include<iostream> using namespace std; int main() { long long i, j, K, L, z, sum = 0; long long dp[500][500]; cin>>K>>L; for(i = 0; i < K; i++) dp[1][i] = 1;//位数为1的所有可能数字全置1 if(L >= 2) { for(i = 2; i <= L; i++)//位数 for(j = 0; j < K; j++)//第一位 for(z = 0; z < K; z++) if(z != j+1&&z != j-1) { dp[i][j] = dp[i][j]+dp[i-1][z]; dp[i][j] = dp[i][j]00000007; } } for(j = 1; j < K; j++) { sum = sum+dp[L][j]; sum = sum00000007; } printf("%lld", sum); return 0; }题意： 有一棵n个结点的树，树上的每个结点都有一个正整数权值，如果一个点被选择了，那么树上和它相邻的点都不能被选择，求选出的点的权值和最大为多少？ 输入格式： 第一行包含一个整数n 第二行包含n个正整数，第i个正整数代表i的权值 接下来有n-1行，每行描述树上的一条边 输出格式: 输出一个整数代表选出点的权值和的最大值 例： 输入: 5 1 2 3 4 5 1 2 1 3 2 4 2 5 输出: 12 本题是一个树型动态规划类型的题目，而且需要较多的C++的知识，倘若没有学习过C++，那这一题需要较多的时间取弄懂。 广度搜索+树形动态规划 分析：首先它是一个树形结构，我们可以从上往下看，采用一个二维数组dp[ ][ ]，dp[i][1]代表此结点被选择，dp[i][0]代表此结点不被选择，如果dp[i][1]，那么此时再进行选择时dp[j][0]，因为相邻的结点不会被选择，如果dp[i][0]，则下一个结点可能被选择即dp[j][0]，也可能不被选择即dp[j][0]，则dp[i][1]+ ∑ d p [ j ] [ 0 ] \sum dp[j][0] ∑dp[j][0]、dp[i][0]+ ∑ m a x ( d p [ j ] [ 0 ] , d p [ j ] [ 1 ] ) \sum max(dp[j][0], dp[j][1]) ∑max(dp[j][0],dp[j][1])为其状态转移方程。
#include<bits/stdc++.h> using namespace std; vector <int> G[100001]; int dp[100001][2]; void dfs(int cur, int fa); int main() { int n, i; int u, v; cin>>n; for(i = 1; i <= n; i++) cin>>dp[i][1]; for(i = 1; i < n; i++) { cin>>u>>v; G[u].push_back(v); G[v].push_back(u); } dfs(1, 0); cout<<max(dp[1][0], dp[1][1]); return 0; } void dfs(int cur, int fa) { for(int i = 0; i < G[cur].size(); i++) { int v = G[cur][i]; if(v == fa) continue; dfs(v, cur); //状态方程 dp[cur][1] = dp[cur][1]+dp[v][0]; dp[cur][0] = dp[cur][0]+max(dp[v][0], dp[v][1]); } }