一、背包问题

背包问题描述：有编号分别为a,b,c,d,e的五件物品，它们的重量分别是2,2,6,5,4，它们的价值分别是6,3,5,4,6，每件物品数量只有一个，现在给你个承重为10的背包，如何让背包里装入的物品具有最大的价值总和？

动态规划的基本思路：将该问题转换成子问题，考虑五件物品在给定承重 C 的背包下最大价值为原问题，如下表所示，即为考虑abcde，C = 10时的最大价值，假设为f[5][10]，原问题的解可以分解为两种情况，第一种情况是不考虑放入a只考虑放入bcde承重为C时的最大价值f[4][C],第二种情况是考虑放入a时的最大价值，即value[a]+f[4][10-weight[a]]。 原问题的解f[5][10]取上述两种情况中的最大值，即f[5][10] = max{f[4][10], (f[4][10-weight[a]+value[a]))}。 由此可以看出里面涉及到需要计算f[4][10]和f[4][10-weight[a]]即f[4][4]等子问题。 以此类推，自顶向下的分析可以看出原问题需要子问题的解，我们需要先计算出子问题的解，自底向上求解。求解方式如下表所示，顺序是自底向上、从左往右，或者从左往右、自底向上都可以。注意此问题中的abcde可以包含相同的物件，它们之间的顺序也可以是任意的，不影响最终的结果。
 

#include <iostream>
using namespace std;


int knapsack(int *W, int *V, int *res, int n, int C)
{
    int value = 0;
    int **f = new int*[n];
    for(int i = 0; i < n; i++)
    {
        f[i] = new int[C+1];
    }

    for(int i = 0; i < n; i++)
        for(int j = 0; j <= C;j++)
            f[i][j] = 0;

    for(int i = 0; i < n; i++)
    {
        f[i][0] = 0;
    }
    for(int i = 1; i <= C; i++)
    {
        f[0][i] = (i < W[0])?0:V[0];
    }
    for(int i = 1; i < n; i++)
    {
        for(int y = 1; y <= C; y++)
        {
            if(y >= W[i])
            {
                f[i][y] = (f[i-1][y] > (f[i-1][y-W[i]] + V[i]))?f[i-1][y]:(f[i-1][y-W[i]] + V[i]);
            } else {
                f[i][y] = f[i-1][y];
            }
        }
    }

    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < C+1;j++)
           cout << f[i][j] << " ";
        cout << endl;
    }

    value = f[n-1][C];
    int j = n-1;
    int y = C;
    while(j)
    {
        if(f[j][y] == (f[j-1][y-W[j]] + V[j]))
        {
            res[j] = 1;
            y = y - W[j];
        }
        j--;
    }
    if(f[0][y])
    {
        res[0] = 1;
    }

    for(int i = 0; i < n;i++)
    {
        delete f[i];
        f[i] = 0;
    }
    delete [] f;
    f = 0;
    return value;
}

void test1()
{
    int n, C;
    while(cin >> n >> C)
    {
        int *W = new int[n];
        int *V = new int[n];
        int *res = new int[n];
        for(int i = 0; i < n; i++)
        {
            res[i] = 0;
        }
        int w = 0, v = 0, i = 0;
        while(i < n)
        {
            cin >> w >> v;
            W[i] = w;
            V[i] = v;
            i++;
        }
        int value = knapsack(W, V, res, n, C);
        cout << value << endl;
        for(int i = 0; i < n; i++)
            cout << res[i] << " ";
        cout << endl;
        delete W;
        delete V;
        delete res;
    }
}

int main()
{
    test1();
    return 0;
}

参考链接：https://blog.****.net/na_beginning/article/details/62884939

二、132-分割回文串

代码：

class Solution(object):
    def minCut(self, s):
        """
        :type s: str
        :rtype: int
        """
        if not s:
            return 0
        
        s_len = len(s)
        mem = [i for i in range(-1, s_len)]
        
        for i in range(1, s_len+1):
            for j in range(i):
                if s[j:i] == s[j:i][::-1]:
                    mem[i] = min(mem[i], mem[j] + 1)
                    
        return mem[-1]

运行结果：