走方格问题
#include <stdio.h>
int v1[3][5] = { {1,5,7,6,8},{4,7,4,4,9},{10,3,2,3,2} };
int v2[3][5] = {0};
int min(int a, int b)
{
return a < b ? a : b;
}
/*
* 给定m行n列的网格,每个格子(i, j)里都一个非负数v[i][j]
* 求一个从左上角(0, 0)到右下角的路径,每一步只能向下或者向右走一步
* 使得路径上的格子里的数字之和最小
* 输出最小数字和
*
* 通过动态规划进行计算
* f(n,m) = min(f(n, m - 1), f(n - 1, m)) + v[n][m]
* f(n,m)的前一步,是向上或者向左走,取最小值
* 特殊情况:
* 1. f(0,0) = v[0][0]
* 2. n == 0 或 m == 0, 则只能选择一边
*/
int get_min_by_dp(int n, int m)
{
if (n == 0 && m == 0) {
v2[0][0] = v1[0][0];
return v2[0][0];
}
if (n == 0) {
v2[n][m] = get_min_by_dp(n, m - 1) + v1[n][m];
return v2[n][m];
}
if (m == 0) {
v2[n][m] = get_min_by_dp(n - 1, m) + v1[n][m];
return v2[n][m];
}
int d1 = get_min_by_dp(n - 1, m);
int d2 = get_min_by_dp(n, m - 1);
v2[n][m] = min(d1, d2) + v1[n][m];
return v2[n][m];
}
int main()
{
int min = get_min_by_dp(2, 4);
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 5 ; j++) {
printf("%d(%d)\t", v1[i][j], v2[i][j]);
}
printf("\n");
}
printf("%d\n", min);
return 0;
}
数字解密问题
#include <stdio.h>
#include <string.h>
#include <malloc.h>
#include <memory.h>
/*
* 有一段A-Z组成字母信息串被加密数字串,加密方式A-1,B-2...给定加密后的数字串有多少种解密方式?
* 加密方式为:A->1, B->2, …, Z->26
*
* 设数字串长度为N,要求数字串前N个字符的解密方式数,需要知道数字串前N-1和N-2个字符的解密方式数。
* 状态:设数字串S前 i 个数字解密成字母串有 f[i] 种方式。
*
* 转移方程:
* f(i) = f(i-1) | s[i-1] + f(i-2) | s[i-2]s[i-1]
*
* 初始值:
* f(0) = 1,空串是一种解密
*
* 边界:
* f(1) = 1,只有一个数字,也能转换为一个字母
*/
int get_case(char *s)
{
int len = strlen(s);
if (len == 0) {
return 1;
}
int *f = (int *)malloc(len+1);
if (f == NULL) {
return 0;
}
f[0] = 1;
f[1] = 1;
for (int i = 2; i < len + 1; i++) {
f[i] = 0;
// 一个字母时:
if (s[i-1] >= '0' && s[i-1] <= '9') {
f[i] += f[i-1];
}
//两个字母时:
if ((s[i-2] == '1' || s[i-2] == '2') &&
(s[i-1] >= '0' && s[i-1] <= '6')) {
f[i] += f[i-2];
}
printf("f(%d):%d\n", i, f[i]);
}
return f[len];
}
int main()
{
char *s = "122227";
int num = get_case(s);
printf("%d\n", num);
}
区间型动态规划
最少平方数
#include <vector>
#include <iostream>
using namespace std;
/**
* 给定一个正整数n,问最少可以将n分成几个完全平方数(1,4,9,...)之和?
*
* 关注最优策略中最后一个完全平方数 j2,最优策略中n-j2 也一定被分成最少的完全平方数之和。
* 所以需要知道n-j2 最少被分成几个完全平方数之和。原来是求 n 最少被分成几个完全平方数之和。
* 状态:设 f[i] 表示 i 最少被分成几个完全平方数之和
*
* 转移方程:
* f[i] = min(f[i+j*j] + 1), 1 <= j*j <= i
*/
int get_min_num(int n)
{
vector<int> f(n+1);
f[0] = 0;
f[1] = 1;
for (int i = 2; i < n + 1; i++) {
int min = 0x7FFFFFFF;
for (int j = 1; j < i / 2 + 1; j++) {
if (i < j * j) {
break;
}
int temp = f[i - j * j];
min = min > temp ? temp : min;
}
f[i] = min + 1;
printf("f(%d):%d\n", i, f[i]);
}
return f[n];
}
int main()
{
int min = get_min_num(10);
printf("min=%d\n", min);
}
最少回文切割问题
#include <iostream>
#include <vector>
#include <string.h>
using namespace std;
/**
* 给定一个字符串s[0...N-1],要求将这个字符串划分成若干段,每段都是一个都是一个回文串(正反看起来都一样)龟最少划分多少次?
* 如:"aab" 划分最少1次,"aa","b"
*
* 确定状态:
* 最后一步:关注最优策略中最后一段的回文,为s[j...N-1]
* 子问题:求s前N个字符s[0...N-1]最少划分几个回文,需要知道s前j个字符,最少划分成几个回文。
* 状态:设s前i个字符s[0...i-1],最少可以划分成f[i]个回文
* 转移方程:f[i] = min(f[j]+1,j=0...i-1),且s[j...i-1]是回文串
*/
int get_min_cut(char *s)
{
int n = strlen(s);
vector<vector<int>> p(n, vector<int> (n));
for (int i = n - 1 ; i >= 0; i--) {
// 记录i开始,到j结束的字符串是否是回文
for (int j = i; j <= n - 1; j++) {
if (s[i] == s[j] && (j - i < 2 || p[i+1][j-1] == 1)) {
p[i][j] = 1;
printf("%d,%d\n", i, j);
}
}
}
vector<int> f(n+1);
f[0] = 0;
f[1] = 1;
for(int i = 2; i <= n; i++) {
int min = 0x7FFFFFFF;
for (int j = 0; j < i; j++) {
if (p[j][i-1] == 1) {
min = f[j] + 1 < min ? f[j] + 1 : min;
}
}
f[i] = min;
printf("f(%d):%d\n", i,f[i]);
}
return f[n] - 1;
}
int main()
{
int num = get_min_cut("aaa");
printf("num=%d\n", num);
}