題意
給你一個(gè)01構(gòu)成的數(shù)組上真。請你找出最小翻轉(zhuǎn)步數(shù)，使得數(shù)組滿足以下規(guī)則：
1的后面可以是1或者0匙奴，但是0的后面必須是0魄健。
樣例
給出 array = [1,0,0,1,1,1] , 返回2。
解釋：
把兩個(gè)0翻轉(zhuǎn)成1旋奢。
給出 array = [1,0,1,0,1,0] , 返回2泳挥。
解釋：
把第二個(gè)1和第三個(gè)1都翻轉(zhuǎn)成0。
注意事項(xiàng)
輸入的數(shù)組長度n <= 100000
1.解題思路
??這道題是一道非常簡單的動(dòng)態(tài)規(guī)劃題至朗。不得不欣慰屉符，自己花了不到20分鐘的事件，把這道題做出來了锹引，自己的動(dòng)態(tài)規(guī)劃終于好了那么一點(diǎn)點(diǎn)了矗钟！
??由于這道題非常的簡單，這里我簡單的介紹一下這道題的思路嫌变。假設(shè)dp[nums.length][2]吨艇，其中dp[i][0],表示第i張牌變成0需要的最小步數(shù)，dp[i][1]意思也是如此初澎。
??其中我們從題意中得到秸应，1只能在1后面的，不能再0的后面碑宴。所以當(dāng)nums[i] =1,dp[i][1] = dp[i - 1][1]這個(gè)肯定是正確的，但是dp[i ][0],由于nums為1桑谍，所以變?yōu)?需要需要旋轉(zhuǎn)一次延柠。從而得知，dp[i][0] = Math.min(dp[i - 1][1] + 1, dp[i - 1][0] + 1),首先從0到1锣披，肯定會(huì)增加一步贞间；其次0可以在1或者0的后面，所以雹仿，需要從上一步中取最小增热。
??當(dāng)nums[i]= 0時(shí)，我們知道的值0可以在1或者0的后面胧辽，所以峻仇，dp[i][0] = Math.min(dp[i - 1][0], dp[i - 1][1])；同時(shí)我們還知道邑商，1只能在1的后面摄咆，所以dp[i][1] = dp[i -1] + 1,這里之所以+1是因?yàn)閚ums[i]本來為1凡蚜，要想變?yōu)閐p[i][0]需要旋轉(zhuǎn)一步。
2.代碼
public int flipDigit(int[] nums) {
int dp[][] = new int[nums.length][2];
if (nums[0] == 1) {
dp[0][1] = 0;
dp[0][0] = 1;
} else {
dp[0][0] = 0;
dp[0][1] = 1;
}
for (int i = 1; i < nums.length; i++) {
if (nums[i] == 1) { //當(dāng)nums[i] = 1時(shí)
//從1 變?yōu)?需要增加一步吭从，同時(shí)0可以在1或者0的后面朝蜘，所以需要取最小值
dp[i][0] = Math.min(dp[i - 1][1] + 1, dp[i - 1][0] + 1);
//不變，繼承上一步
dp[i][1] = dp[i - 1][1];
} else {
//0可以在1或者0的后面涩金，由于它本身就是0谱醇，所以不需要增加步數(shù)
dp[i][0] = Math.min(dp[i - 1][0], dp[i - 1][1]);
//從0變?yōu)?需要增加步數(shù)
dp[i][1] = dp[i - 1][1] + 1;
}
}
return Math.min(dp[nums.length - 1][0], dp[nums.length - 1][1]);
}
