0 背景

从（完）零（全）开（忘）始（记）温（不）习（会）动（做）态（题）规（！）划。

1 动态规划理解

如果一类活动过程可以分为若干个互相联系的阶段，在每一个阶段都需作出决策(采取措施)，一个阶段的决策确定以后，常常影响到下一个阶段的决策，从而就完全确定了一个过程的活动路线，则称它为多阶段决策问题。
各个阶段的决策构成一个决策序列，称为一个策略。每一个阶段都有若干个决策可供选择，因而就有许多策略供我们选取，对应于一个策略可以确定活动的效果，这个效果可以用数量来确定。策略不同，效果也不同，多阶段决策问题，就是要在可以选择的那些策略中间，选取一个最优策略，使在预定的标准下达到最好的效果.

？？？啥意思？？
下面这一段，我感觉解释并不是很清楚。。所以暂且划掉了
举个例子，以王者农药来说，
选人的时候我们可以选择‘良好的阵容搭配’或者'想玩什么玩什么'
前期的时候我们可以选择'猥琐发育，别浪'或者‘全体进攻中路’
中期的时候我们可以选择‘稳住我们能赢’、'进攻暗影主宰'、'全体进攻中路'、'猥琐发育，别浪'、'清理兵线'、‘投降’
后期的时候。。。
在每一步中我们都可以选择不同的策略，每一步都策略都基于前一步的选择，并且也会影响后面的步骤。
例如
策略：（‘良好的阵容搭配’（决策）+‘猥琐发育’（决策）+‘稳住我们能赢’（决策））= 白金（效果）
。。。
值得注意的是，我们不是每一步都要选择最优的决策，因为，可能当前决策不是最好的，但是我们最终效果确实最好的。
例如
'良好的阵容搭配'是选人最好的决策，但是我就只会玩阿珂，魔都第一阿珂，但是已经有刺客了，我还是会选阿珂（决策），因为选了阿珂就赢了。。（只是举个例子），虽然在选人阶段我们没有选择最优的决策，但是我们最后的效果是最好的。

2 思路

基于上面的理解，我们做题该如何去做呢？

1.将大问题拆解为一个个的子问题，

2.求解每个子问题，并将其结果保存在一个表中，以后用到时到时直接存取，不重复计算，节省计算时间

3.自下而上的计算

3 题目

某厂笔试题目，大概题意，排成一行的正方形，每个正方形已经被染成红色或者绿色。现在可以选择任意一个正方形然后用这两种颜色的任意一种进行染色，这个正方形的颜色将会被覆盖。目标是在完成染色之后，每个红色R逗比每个绿色G距离最左侧近，最少需要染几个正方形。
样例 s=RGRGR
我们涂色之后变成RRRGG满足要求，涂染的次数是2，没有比这个更好的涂染方案了（这是原题的话，其实还有别的涂染方案呀，RGGGG也是2次，RRRRR也是2次）
输入描述：

输入包括一个字符串S，字符串s的长度（1<=length<=50）,其中包括'R'或者‘G’，分别表示红色和绿色

输出描述

输出一个整数，表示最少需要涂染的正方形数量

4 题目分析

其实这道题在字符串很短的时候，我们用人脑很好思考，
例如
RGGGR 我们只需要把最后一个R涂成G即满足要求
RGRRR 我们只需要吧第二个G涂成R即满足要求
但是我们怎么将我们脑子里面的计算方法转换成电脑能识别的程序语言呢？毕竟当字符串的数量很多的时候，我们也没有办法用我们的大脑很快计算出结果。例如
RGRGRRRRGGGGGRGRGGRRRRRGRGRRRRGGGGGRGRGGRRRRRGRGRRRRGGGGGRGRGGRRRRRGRGRRRRGGGGGRGRGGRRRR
言归正传，用动态规划的想法去思考这道题呢？

输入RGGGR，
我们这道题的子问题是什么呢？就是每一个方块该涂什么颜色，自下而上，那我们这里就是自左而右

第一个R，我们有两种决策,这个次数我们要记下来

1.1.涂成R （0次）
1.2.涂成G（1次）

第二个G，我们仍有两种决策，而到这一步的决策我们需要的次数就要跟上一步有关了

2.1 涂成R
如果上一次使用1.1的策略我们只需要把第二个G涂成R即可，也就是1次，如果上一次使用1.2的策略我们需要把第一个先涂成R，再把第二个G涂成R也就是2次，这里我们肯定选择1.1的策略，因为选择1.1或者选择1.2，到了2.1，前两个的正方形都是RR所以我们选择1.2的策略划横线的说法是不对的，每一小步的决策不能修改上一步的决策，意思是什么呢？如果我们这一步选择2.1我们就在1.2的基础上了，因为R必须在G的左边（1次）
2.2 涂成G
如果上一次使用1.1的策略我们本来就是RG所以是0次，如果使用1.2的策略我们是GG所以要把第一个G涂成R，是1次，所以我们肯定选择1.1，为什么说肯定呢，到第三个方块的时候，它已经不关心第一个方块到到底是R还是G了，因为第二个方块是G，它已经给第三个方块提供了决策的基础，所以我们只需要在这一步上选择最优的（0次）

第三个G

3.1涂成R
如果上一次使用2.1的话，我们只需要将第三个涂成R也就是再增加一次2次，如果上一次使用2.2，我们不能选择3.1（2次）
3.2涂成G
如果上一次使用2.1的话，我们就在2.1的基础上+0也就是1次，如果上一次使用2.2的话，我们在2.2的基础上+0也就是0次，选择最优的（0次）

第四个G

4.1涂成R
如果上一次使用3.1的话，我们只需要将第三个涂成R也就是再增加一次3次，如果上一次使用3.2，我们不能选择4.1（3次）
4.2涂成G
如果上一次使用3.1的话，我们就在3.1的基础上+0也就是2次，如果上一次使用3.2的话，我们在3.2的基础上+0也就是0次，选择最优的（0次）

第五个G

5.1涂成R
如果上一次使用4.1的话，我们只需要将第三个涂成R也就是再增加0次3次，如果上一次使用4.2，我们不能选择5.1（3次）
5.2涂成G
如果上一次使用3.1的话，我们就在3.1的基础上+1也就是4次，如果上一次使用3.2的话，我们在3.2的基础上+1也就是1次，选择最优的（1次）
如果我们到这里结束，我们只需要比较5.1和5.2的大小，选择小的就是5.2

5 代码

import java.util.Scanner;

public class dpTest {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String input = scanner.nextLine();
        int len = input.length();
        int[][] dp = new int[2][len+1];
        dp[0][0] = input.charAt(0) == 'R' ? 0 : 1;
        dp[1][0] = input.charAt(0) == 'R' ? 0 : 1;
        for (int i = 1; i < len; ++i) {
            dp[0][i] = dp[0][i - 1] + (input.charAt(i) == 'R' ? 0 : 1);
            dp[1][i] = Math.min(dp[1][i - 1], dp[0][i - 1]) + (input.charAt(i) == 'R' ? 1 : 0);
        }
//如果你想详细看dp的情况可以把下面的注释去掉
//        for (int[] ints : dp) {
//            for (int anInt : ints) {
//                System.out.print(anInt + "\t");
//            }
//            System.out.println();
//        }
        System.out.println(Math.min(dp[0][len - 1], dp[1][len - 1]));
    }
}

希望自己能给和自己一样菜的同学，一点点生存的空间，欢迎热烈讨论

我是加薪猫
技术是加薪的前提，生活是加薪的意义
技术等于生活

动态规划浅入浅出（一）涂色问题