动态规划

| 分类 算法  | 标签 动态规划 

走方格问题

#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);
}

上一篇     下一篇