最大利润-城市A和B

1，问题描述

jack每天同时只能在A和B其中一个城市工作赚钱，假设两个城市间的交通费为m。已知每天在A 和 B 能赚到多少钱，那么jack怎么选择每天工作的城市才能赚到最大利润。

比如 moneyA = {1，2，3，4，3，1}；moneyB = {2，1，3，4，2，1}；m = 1。

2，边界条件：无

3，思路：假设某一天jack在A城市工作，那么接下来怎么选择到最后一个才能赚到最多，在B城市类似。然后形成递归。

4，代码实现

1）简单递归

 1     public static void main(String[] args) {
 2         int[] cityA = {1,2,4,5,6,3,1};
 3         int[] cityB = {2,3,4,5,1,1,2};
 4         int res = Math.max(mostMoney(cityA, cityB, 1, 0), mostMoney(cityB, cityA, 1, 0));
 5         System.out.println("res: " + res);
 6     }
 7 
 8     public static int mostMoney(int[] curCity, int[] nextCity, int m, int idx) {
 9         if (idx >= curCity.length) {
10             return 0;
11         }
12 
13         int moneyCur = mostMoney(curCity, nextCity, m, idx + 1);
14         int moneyNext = mostMoney(nextCity, curCity, m, idx + 1) - m;
15         return curCity[idx] + Math.max(moneyCur, moneyNext);
16     }

2）其实在递归时在某一个点能获取的最大利润重复计算，所以获得该最大利润后需记录下来cache，下次直接用，这就是动态规划DP。

 1     private static int[] recA;
 2     private static int[] recB;
 3     public static void main(String[] args) {
 4         int[] cityA = {1,2,4,5,6,3,1};
 5         int[] cityB = {2,3,4,5,1,1,2};
 6         recA = new int[cityA.length];
 7         recB = new int[cityB.length];
 8         recA[0] = mostMoney(cityA, cityB, true, 1, 0);
 9         recB[0] = mostMoney(cityB, cityA, false, 1, 0);
10         int res = Math.max(recA[0], recB[0]);
11         System.out.println("res: " + res);
12         System.out.println("recA: " + Arrays.toString(recA));
13         System.out.println("recB: " + Arrays.toString(recB));
14     }
15 
16     public static int mostMoney(int[] curCity, int[] nextCity, boolean isCityA, int m, int idx) {
17         if (idx >= curCity.length) {
18             return 0;
19         }
20         if (isCityA && recA[idx] != 0) {
21             return recA[idx];        
22         } else if (recB[idx] != 0) {
23             return recB[idx];
24         }
25 
26         int moneyCur = mostMoney(curCity, nextCity, isCityA, m, idx + 1);
27         int moneyNext = mostMoney(nextCity, curCity, !isCityA, m, idx + 1) - m;
28         int mostCur = curCity[idx] + Math.max(moneyCur, moneyNext);
29         if (isCityA == true) {
30             recA[idx] = mostCur;
31         } else {
32             recB[idx] = mostCur;
33         }
34 
35         return  mostCur;
36     }

3）记录下来之后，写成非递归形式

 1     private static int[] recA;
 2     private static int[] recB;
 3     public static void main(String[] args) {
 4         int[] cityA = {1,2,4,5,6,3,1};
 5         int[] cityB = {2,3,4,5,1,1,2};
 6         int m = 1;
 7         recA = new int[cityA.length];
 8         recB = new int[cityB.length];
 9         recA[cityA.length - 1] = cityA[cityA.length - 1];
10         recB[cityB.length - 1] = cityB[cityB.length - 1];
11         for (int i = cityA.length - 2; i >= 0; i--) {
12             recA[i] = cityA[i] + Math.max(recA[i + 1], recB[i + 1] - m);
13             recB[i] = cityB[i] + Math.max(recA[i + 1] - m, recB[i + 1]);
14         }
15         int res = Math.max(recA[0], recB[0]);
16         System.out.println("res: " + res);
17         System.out.println("recA: " + Arrays.toString(recA));
18         System.out.println("recB: " + Arrays.toString(recB));
19     }

5，时间复杂度：非递归形式是O（n）

6，api：无